How can I fix my C++ code that determines whether a number is prime? [closed]

bool isPrime(int number){ if(number < 2) return false; if(number == 2) return true; if(number % 2 == 0) return false; for(int i=3; (i*i)<=number; i+=2){ if(number % i == 0 ) return false; } return true; } 

My own IsPrime() function, written and based on the deterministic variant of the famous Rabin-Miller algorithm, combined with optimized step brute forcing, giving you one of the fastest prime testing functions out there.

__int64 power(int a, int n, int mod) { __int64 power=a,result=1; while(n) { if(n&1) result=(result*power)%mod; power=(power*power)%mod; n>>=1; } return result; } bool witness(int a, int n) { int t,u,i; __int64 prev,curr; u=n/2; t=1; while(!(u&1)) { u/=2; ++t; } prev=power(a,u,n); for(i=1;i<=t;++i) { curr=(prev*prev)%n; if((curr==1)&&(prev!=1)&&(prev!=n-1)) return true; prev=curr; } if(curr!=1) return true; return false; } inline bool IsPrime( int number ) { if ( ( (!(number & 1)) && number != 2 ) || (number < 2) || (number % 3 == 0 && number != 3) ) return (false); if(number<1373653) { for( int k = 1; 36*k*k-12*k < number;++k) if ( (number % (6*k+1) == 0) || (number % (6*k-1) == 0) ) return (false); return true; } if(number < 9080191) { if(witness(31,number)) return false; if(witness(73,number)) return false; return true; } if(witness(2,number)) return false; if(witness(7,number)) return false; if(witness(61,number)) return false; return true; /*WARNING: Algorithm deterministic only for numbers < 4,759,123,141 (unsigned int's max is 4294967296) if n < 1,373,653, it is enough to test a = 2 and 3. if n < 9,080,191, it is enough to test a = 31 and 73. if n < 4,759,123,141, it is enough to test a = 2, 7, and 61. if n < 2,152,302,898,747, it is enough to test a = 2, 3, 5, 7, and 11. if n < 3,474,749,660,383, it is enough to test a = 2, 3, 5, 7, 11, and 13. if n < 341,550,071,728,321, it is enough to test a = 2, 3, 5, 7, 11, 13, and 17.*/ } 

To use, copy and paste the code into the top of your program. Call it, and it returns a BOOL value, either true or false.

if(IsPrime(number)) { cout << "It's prime"; } else { cout<<"It's composite"; } 

If you get a problem compiling with "__int64", replace that with "long". It compiles fine under VS2008 and VS2010.

How it works: There are three parts to the function. Part checks to see if it is one of the rare exceptions (negative numbers, 1), and intercepts the running of the program.

Part two starts if the number is smaller than 1373653, which is the theoretically number where the Rabin Miller algorithm will beat my optimized brute force function. Then comes two levels of Rabin Miller, designed to minimize the number of witnesses needed. As most numbers that you'll be testing are under 4 billion, the probabilistic Rabin-Miller algorithm can be made deterministic by checking witnesses 2, 7, and 61. If you need to go over the 4 billion cap, you will need a large number library, and apply a modulus or bit shift modification to the power() function.

If you insist on a brute force method, here is just my optimized brute force IsPrime() function:

inline bool IsPrime( int number ) { if ( ( (!(number & 1)) && number != 2 ) || (number < 2) || (number % 3 == 0 && number != 3) ) return (false); for( int k = 1; 36*k*k-12*k < number;++k) if ( (number % (6*k+1) == 0) || (number % (6*k-1) == 0) ) return (false); return true; } } 

How this brute force piece works: All prime numbers (except 2 and 3) can be expressed in the form 6k+1 or 6k-1, where k is a positive whole number. This code uses this fact, and tests all numbers in the form of 6k+1 or 6k-1 less than the square root of the number in question. This piece is integrated into my larger IsPrime() function (the function shown first).

If you need to find all the prime numbers below a number, find all the prime numbers below 1000, look into the Sieve of Eratosthenes. Another favorite of mine.

As an additional note, I would love to see anyone implement the Eliptical Curve Method algorithm, been wanting to see that implemented in C++ for a while now, I lost my implementation of it. Theoretically, it's even faster than the deterministic Rabin Miller algorithm I implemented, although I'm not sure if that's true for numbers under 4 billion.

I would guess taking sqrt and running foreach frpm 2 to sqrt+1 if(input% number!=0) return false; once you reach sqrt+1 you can be sure its prime.

C++

bool isPrime(int number){ if (number != 2){ if (number < 2 || number % 2 == 0) { return false; } for(int i=3; (i*i)<=number; i+=2){ if(number % i == 0 ){ return false; } } } return true; } 

If you know the range of the inputs (which you do since your function takes an int), you can precompute a table of primes less than or equal to the square root of the max input (2^31-1 in this case), and then test for divisibility by each prime in the table less than or equal to the square root of the number given.

This code only checks if the number is divisible by two. For a number to be prime, it must not be evenly divisible by all integers less than itself. This can be naively implemented by checking if it is divisible by all integers less than floor(sqrt(n)) in a loop. If you are interested, there are a number of much faster algorithms in existence.

If you are lazy, and have a lot of RAM, create a sieve of Eratosthenes which is practically a giant array from which you kicked all numbers that are not prime. From then on every prime "probability" test will be super quick. The upper limit for this solution for fast results is the amount of you RAM. The upper limit for this solution for superslow results is your hard disk's capacity.

Use mathematics first find square root of number then start loop till the number ends which you get after square rooting. check for each value whether the given number is divisible by the iterating value .if any value divides the given number then it is not a prime number otherwise prime. Here is the code

 bool is_Prime(int n) { int square_root = sqrt(n); // use math.h int toggle = 1; for(int i = 2; i <= square_root; i++) { if(n%i==0) { toggle = 0; break; } } if(toggle) return true; else return false; } 

I follow same algorithm but different implementation that loop to sqrt(n) with step 2 only odd numbers because I check that if it is divisible by 2 or 2*k it is false. Here is my code

public class PrimeTest { public static boolean isPrime(int i) { if (i < 2) { return false; } else if (i % 2 == 0 && i != 2) { return false; } else { for (int j = 3; j <= Math.sqrt(i); j = j + 2) { if (i % j == 0) { return false; } } return true; } } /** * @param args */ public static void main(String[] args) { for (int i = 1; i < 100; i++) { if (isPrime(i)) { System.out.println(i); } } } } 

bool check_prime(int num) { for (int i = num - 1; i > 1; i--) { if ((num % i) == 0) return false; } return true; } 

checks for any number if its a prime number

There are several different approches to this problem.
The "Naive" Method: Try all (odd) numbers up to (the root of) the number.
Improved "Naive" Method: Only try every 6n ± 1.
Probabilistic tests: Miller-Rabin, Solovay-Strasse, etc.

Which approach suits you depends and what you are doing with the prime.
You should atleast read up on Primality Testing.

If n is 2, it's prime.

If n is 1, it's not prime.

If n is even, it's not prime.

If n is odd, bigger than 2, we must check all odd numbers 3..sqrt(n)+1, if any of this numbers can divide n, n is not prime, else, n is prime.

For better performance i recommend sieve of eratosthenes.

Here is the code sample:

bool is_prime(int n) { if (n == 2) return true; if (n == 1 || n % 2 == 0) return false; for (int i = 3; i*i < n+1; i += 2) { if (n % i == 0) return false; } return true; } 

Count by 6 for better speed:

bool isPrime(int n) { if(n==1) return false; if(n==2 || n==3) return true; if(n%2==0 || n%3==0) return false; for(int i=5; i*i<=n; i=i+6) if(n%i==0 || n%(i+2)==0) return false; return true; } 

Here is a C++ code to determine that a given number is prime:

bool isPrime(int num) { if(num < 2) return false; for(int i = 2; i <= sqrt(num); i++) if(num % i == 0) return false; return true; } 

PS Don't forget to include math.h library to use sqrt function

There are many potential optimization in prime number testing.

Yet many answers here, not only are worse the O(sqrt(n)), they suffer from undefined behavior (UB) and incorrect functionality.

A simple prime test:

// Return true when number is a prime. bool is_prime(int number) { // Take care of even values, it is only a bit test. if (number % 2 == 0) { return number == 2; } // Loop from 3 to square root (n) for (int test_factor = 3; test_factor <= number / test_factor; test_factor += 2) { if (number % test_factor == 0) { return false; } } return n > 1; } 

• Do not use test_factor * test_factor <= number. It risks signed integer overflow (UB) for large primes.

• Good compilers see nearby number/test_factor and number % test_factor and emit code that computes both for the about the time cost of one. If still concerned, consider div().

• Avoid sqrt(n). Weak floating point libraries do not perform this as exactly as we need for this integer problem, possible returning a value just ever so less than an expected whole number. If still interested in a sqrt(), use lround(sqrt(n)) once before the loop.

• Avoid sqrt(n) with wide integer types of n. Conversion of n to a double may lose precision. long double may fair no better.

• Test to insure the prime test code does not behave poorly or incorrectly with 1, 0 or any negative value.

• Consider bool is_prime(unsigned number) or bool is_prime(uintmax_t number) for extended range.

• Avoid testing with candidate factors above the square root n and less than n. Such test factors are never factors of n. Not adhering to this makes for slow code.

• A factor is more likely a small value that an large one. Testing small values first is generally far more efficient for non-primes.

• Pedantic: Avoid if (number & 1 == 0) {. It is an incorrect test when number < 0 and encoded with rare ones' complement. Use if (number % 2 == 0) { and trust your compiler to emit good code.

More advanced techniques use a list of known/discovered primes and the Sieve of Eratosthenes.

OK I fixed up your functions somewhat.

• Check if number is less than 2 If so not prime
• Check if it is 2 or 3, if so prime
• Then check if the number%6 is 1 or 5 If it is not and it is >3 it cannot be prime All primes > 3 are 6k plus or minus 1. So they are like 5,11,17 %6 = 5 or like 7,13,19 %6 = 1. This will get rid of 2/3 of numbers right here.
• All the primes left will be 6k plus or minus one. So lets divide by those numbers to look for failures. We loop from 5 to the square root of the number by 6. So p will be 5,11,17,23 and p+2 will be 7,13,19,25 and so on. Another 20% will be eliminated by the first divide, i%5==0
• If nothing has divided evenly we have a prime.

void primenumber(int number) { if (number < 2) cout<< number << " is NOt prime"<<endl; else if (number == 2 || number ==3) cout<< number << " is prime:"<<endl; else if (!(number%6==1 || number%6==5)) cout<< number << " is NOt prime"<<endl; else { for (int p = 5;p <= (int)sqrt(number)+1;p+=6) if (number%p ==0 || number%(p+2)==0) { cout<< number << " is NOt prime"<<endl; return; } cout<< number << " is prime:"<<endl; } return; } 

If you don't want to do all of the cout code inside the prime check, the logic becomes very easy:

int IsPrime(long long N) { if (N <= 3) return N > 1; if (!(N%6==1 || N%6==5)) return false; for (long long k6=5; k6 <= (long long)sqrt(N) + 1; k6+=6) if (N%k6==0 || N%(k6+2)==0) return false; // just 6k±1 return true; } 

user6449382's answer had the following:

bool check_prime(int num) { for (int i = num - 1; i > 1; i--) { if ((num % i) == 0) return false; } return true; } 

This mostly worked when I tested it in Visual Studio 2017. It would say that anything less than 2 was also prime (so 1, 0, -1, etc.)

Here is a slight modification to correct this.

bool check_prime(int number) { if (number > 1) { for (int i = number - 1; i > 1; i--) { if ((number % i) == 0) return false; } return true; } return false; }