Determining if a number is prime

Question

I looked through a lot of code on this topic, but most of them produce numbers that are first, right down to the input number. However, I need a code that checks if a given input number is simple.

Here is what I was able to write, but it does not work:

void primenumber(int number) { if(number%2!=0) cout<<"Number is prime:"<<endl; else cout<<"number is NOt prime"<<endl; } 

I would appreciate it if someone could give me advice on how to do it right.

Update

I modified it to check all the numbers in a for loop.

 void primenumber(int number) { for(int i=1; i<number; i++) { if(number%i!=0) cout<<"Number is prime:"<<endl; else cout<<"number is NOt prime"<<endl; } } 

Answer 1

You need to do some more checks. Right now, you are only checking to see if the number is divisible by 2. Do the same for 2, 3, 4, 5, 6, ... to number . Hint: use a loop .

After resolving this issue, try to find optimization. Hint: you only need to check all numbers to the square root of the number

Answer 2

 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; } 

Answer 3

My own IsPrime () function, written and based on a deterministic version of the well-known Rabin-Miller algorithm combined with optimized power-law forcing, which provides you with one of the fastest basic testing functions.

 __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 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 at the beginning of your program. Call it and it will return the BOOL value, true or false.

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

If you are having trouble compiling with "__int64", replace it with "long." It compiles for VS2008 and VS2010.

How it works: There are three parts to a function. The part checks whether this is one of the rare exceptions (negative numbers, 1) and intercepts the start of the program.

Part two begins if the number is less than 1373653, which is a theoretical number in which the Rabin Miller algorithm will surpass my optimized brute force function. Then there are two levels of Rabin Miller, designed to minimize the number of witnesses needed. Since most of the numbers you will be testing are less than 4 billion, the Rabin-Miller probabilistic algorithm can be determined by checking witnesses 2, 7 and 61. If you need to list a 4 billion cap, you will need a large one and apply a module or bit shift modification to the power () function.

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

 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 works: All prime numbers (except 2 and 3) can be expressed as 6k + 1 or 6k-1, where k is a positive integer. This code uses this fact and checks all numbers in the form 6k + 1 or 6k-1 less than the square root of the number in question. This part is integrated into my big IsPrime () function (the function shown first).

If you need to find all primes below the number, find all primes below 1000, look into the sieve of Eratosthenes. Another one of my favorites.

As an additional note, I would like someone to implement the Eliptical Curve Method algorithm, which wanted to see what has been implemented in C ++ for a while, I lost my implementation. Theoretically, this is even faster than the Rabin Miller deterministic algorithm that I implemented, although I'm not sure if this is true for numbers up to 4 billion.

Answer 4

I would prefer to take sqrt and run foreach frpm 2 to sqrt + 1 if (input% number! = 0) return false; once you achieve sqrt + 1, you can be sure of its advantage.

Answer 5

If you know the range of inputs (which you do, since your function accepts int ), you can previously copy a prime table less than or equal to the square root of the maximum input (2 ^ 31-1 in this case), and then check the divisibility by each simple in the table, less than or equal to the square root of the number.

Answer 6

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

checks any number if its prime

Answer 7

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; } 

Javascript

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

Python

 def isPrime(number): if (number != 2): if (number < 2 or number % 2 == 0): return False i = 3 while (i*i) <= number: if(number % i == 0 ): return False; i += 2 return True; 

Answer 8

This code only checks if the number is divisible by two. For a number to be simple, it does not have to be evenly divisible by all integers smaller than itself. This can be naively realized by checking if it is divisible by all integers less than floor(sqrt(n)) in the loop. If this interests you, there are a number of much faster algorithms .

Answer 9

If you are lazy and have a lot of RAM, create an Eratosthenes sieve, which is an almost gigantic array from which you kicked all the numbers that are not primary. From now on, every simple probability test will be very fast. The upper limit for this solution for quick results is the amount of RAM you have. The upper limit for this solution for better results is the capacity of your hard drive.

Answer 10

I am executing the same algorithm, but a different implementation that loops on 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); } } } } 

Answer 11

Use the math, first find the square root of the number, then run the loop until the number ends, which you get after square rooting. check for each value whether the given number is divisible by the iterable value. If any value divides a given number, then this is not just a number, it is another 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; } 

Answer 12

Someone above had the following.

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

It basically worked. I just tested it in Visual Studio 2017. It would be said that anything less than 2 was also simple (like 1, 0, -1, etc.)

Here is a small modification to fix 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; } 

Answer 13

See the program here: http://www.cplusplus.com/forum/general/1125/

Answer 14

There are several different approaches to this problem.
Naive Method: Try all (odd) numbers up to (root) numbers.
Improved Naive method: try only every 6n ± 1.
Probability tests: Miller-Rabin, Nightingale-Strasse and others.

Which approach suits you, and what you do with the simple.
You should at least read Priority Testing .

Answer 15

 // PrimeDef.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include<iostream> #include<stdlib.h> using namespace std; const char PRIME = 176; const char NO_PRIME = 178; const int LAST_VALUE = 2000; bool isPrimeNumber( int value ) { if( !( value / 2 ) ) return false; for( int i = 1; ++i <= value / 2; ) if( 0 == value % i ) return false; return true; } int main( int argc, char *argv[ ] ) { char mark; for( int i = -1, count = 1; ++i < LAST_VALUE; count++ ) { mark = NO_PRIME; if( isPrimeNumber( i ) ) mark = PRIME; cout << mark; if(i > 0 && !( count % 50 ) ) cout << endl; } return 0; } 

Answer 16

If n is 2, then it is simple.

If n is 1, it is not easy.

If n is even, it is not easy.

If n is odd, greater than 2, we must check all the odd numbers 3..sqrt (n) +1, if any of these numbers can divide n, n is not prime, otherwise n is prime.

For best performance, I recommend a sieve of eratosthenes.

Here is a sample code:

 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; } 

Answer 17

I came up with this:

 int counter = 0; bool checkPrime(int x) { for (int y = x; y > 0; y--){ if (x%y == 0) { counter++; } } if (counter == 2) { counter = 0; //resets counter for next input return true; //if its only divisible by two numbers (itself and one) its a prime } else counter = 0; return false; } 

Answer 18

I have this idea for searching if the number is clean or not:

 #include <conio.h> #include <iostream> using namespace std; int main() { int x, a; cout << "Enter The No. :"; cin >> x; int prime(unsigned int); a = prime(x); if (a == 1) cout << "It Is A Prime No." << endl; else if (a == 0) cout << "It Is Composite No." << endl; getch(); } int prime(unsigned int x) { if (x == 1) { cout << "It Is Neither Prime Nor Composite"; return 2; } if (x == 2 || x == 3 || x == 5 || x == 7) return 1; if (x % 2 != 0 && x % 3 != 0 && x % 5 != 0 && x % 7 != 0) return 1; else return 0; } 

Answer 19

This is a quick way:

 bool isPrimeNumber(int n) { int divider = 2; while (n % divider != 0) { divider++; } if (n == divider) { return true; } else { return false; } } 

He will begin to find the dividend number n, starting with 2. As soon as he finds one, if this number is n, then it is prime , otherwise it will not.

Answer 20

 //simple function to determine if a number is a prime number //to state if it is a prime number #include <iostream> using namespace std; int isPrime(int x); //functioned defined after int main() int main() { int y; cout<<"enter value"<<endl; cin>>y; isPrime(y); return 0; } //end of main function //-------------function int isPrime(int x) { int counter =0; cout<<"factors of "<<x<<" are "<<"\n\n"; //print factors of the number for (int i =0; i<=x; i++) { for (int j =0; j<=x; j++) { if (i * j == x) //check if the number has multiples; { cout<<i<<" , "; //output provided for the reader to see the // muliples ++counter; //counts the number of factors } } } cout<<"\n\n"; if(counter>2) { cout<<"value is not a prime number"<<"\n\n"; } if(counter<=2) { cout<<"value is a prime number"<<endl; } } 

Answer 21

 #define TRUE 1 #define FALSE -1 int main() { /* Local variables declaration */ int num = 0; int result = 0; /* Getting number from user for which max prime quadruplet value is to be found */ printf("\nEnter the number :"); scanf("%d", &num); result = Is_Prime( num ); /* Printing the result to standard output */ if (TRUE == result) printf("\n%d is a prime number\n", num); else printf("\n%d is not a prime number\n", num); return 0; } int Is_Prime( int num ) { int i = 0; /* Checking whether number is negative. If num is negative, making it positive */ if( 0 > num ) num = -num; /* Checking whether number is less than 2 */ if( 2 > num ) return FALSE; /* Checking if number is 2 */ if( 2 == num ) return TRUE; /* Checking whether number is even. Even numbers are not prime numbers */ if( 0 == ( num % 2 )) return FALSE; /* Checking whether the number is divisible by a smaller number 1 += 2, is done to skip checking divisibility by even numbers. Iteration reduced to half */ for( i = 3; i < num; i += 2 ) if( 0 == ( num % i )) /* Number is divisible by some smaller number, hence not a prime number */ return FALSE; return TRUE; } 

Answer 22

 if(number%2!=0) cout<<"Number is prime:"<<endl; 

The code is incredibly false. 33 is divisible by 2, 16 with a reminder of 1, but this is not a prime number ...