check if its prime. make this faster

general
,
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.

1 Like
2

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

2 Likes
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, ab 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
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.”;

}

1 Like
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

1 Like