Advertisement
montimaj

FERMAT's LITTLE THEOREM

Mar 29th, 2014
91
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.65 KB | None | 0 0
  1. // Generate primes between a and b exclusive and find s=summation(p[i]-1)^p[i] mod p[i]
  2. // http://en.wikipedia.org/wiki/Fermat's_little_theorem
  3.  
  4. #include<iostream>
  5. #include<vector>
  6. #include<cmath>
  7. int main()
  8. {
  9.     int a,b;
  10.     std::cout<<"Enter a and b: \n";
  11.     std::cin>>a>>b;
  12.     std::vector<int> v;
  13.     for(int i=a+1;i<b;++i)
  14.     {
  15.         bool flag=true;
  16.         for(int j=2;j<=sqrt(i) && flag;++j)
  17.             if(i%j==0)
  18.                 flag=false;
  19.         if(flag)
  20.             v.push_back(i);
  21.     }
  22.     long s=0;
  23.     for(std::vector<int>::iterator it=v.begin();it!=v.end();++it)
  24.         s+=(*it)-1;
  25.     std::cout<<"\nSum= "<<s;
  26. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement