Find a prime number between 2 and n ( n will be an input from the user) using th

Question

Find a prime number between 2 and n ( n will be an input from the user) using the Sieve
of Erastothenes algorithm in c++

Explanation / Answer

#include using namespace std; /* This function calculates (ab)%c */ int modulo(int a,int b,int c){ long long x=1,y=a; // long long is taken to avoid overflow of intermediate results while(b > 0){ if(b%2 == 1){ x=(x*y)%c; } y = (y*y)%c; // squaring the base b /= 2; } return x%c; } /* this function calculates (a*b)%c taking into account that a*b might overflow */ long long mulmod(long long a,long long b,long long c){ long long x = 0,y=a%c; while(b > 0){ if(b%2 == 1){ x = (x+y)%c; } y = (y*2)%c; b /= 2; } return x%c; } /* Miller-Rabin primality test, iteration signifies the accuracy of the test */ bool Miller(long long p,int iteration){ if(p

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---