check if its prime. make this faster

c-plus-plus
prime

#1

can you help me make this faster?


constraint

-in loop, int a should always start in 1

for(int a=1;a<=number;a++)
{
if(number%a==0)
{
count1++;
}
}
if(count1 == 2){

cout << "prime" << endl;
}
else{
cout << "not" << endl;
}

Would you explain to me how number/2 or sqrt(number) can help? I’ve been seeing a lot of those while im researching.


#2

To check if a number is prime or not use Primality test for faster results : http://en.wikipedia.org/wiki/Primality_test


#3

Since a number cannot be divided by any no greater than its half other then itself so dividing by two decreases the no comparisons.

If a number n is not a prime, it can be factored into two factors a and b:
n = ab
If both a and b were greater than the square root of n, a
b would be greater than n. So at least one of those factors must be less or equal to the square root of n, and to check if n is prime, we only need to test for factors less than or equal to the square root.


#4

let me give you a complete programme. Correct some mistakes as this comment box don’t allow some syntax. Hope this will help you!
#include< iostream.h>
#include< conio.h>
main()

{

int i,n;

for(i=2;i<=n;i++)

{

if(n%i==0)

break;

}

if(i==n)

cout<<“It is a prime no.”);

else

cout<<“It is a composite no.”;

}


#5

was my answer correct


#6

there are some problem with header files, also you may optimize your code by checking upto sqrt(n)…

above program with proper syntax and working http://ideone.com/j8EoaI.

More optimized code http://ideone.com/Sz6glk