# check if its prime. make this faster

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.

1 Like

To check if a number is prime or not use Primality test for faster results : Primality test - Wikipedia

2 Likes

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.

1 Like

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.”;

}

1 Like

was my answer correct

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

1 Like