# for loop to find prime numbers

• 10-20-2005
1rwhites
for loop to find prime numbers
For my program, I need to check whether a number is prime or not. I have to use a for loop. And I only have to check for divisors that are less then or equal to the square root of the number being tested. Does anybody know how to do this?

• 10-20-2005
Just run the for loop. With every cycle take the number you are testing and check for remainders when you divide by the number the for loop is on.

Code:

for(int i = 0; i < TestNumber; i++)
{
if(TestNumber % i == 0)
{
//The number is not prime
}
}

That should give you a good start.
• 10-20-2005
1rwhites
OK here is what I have now

Code:

#include <stdio.h> /* define fopen,fclose,fscanf,fprintf */
#include <math.h> /* sqrt definition */
#define TRUE 1
#define FALSE 0

int is_prime(int num);

int main(void)
{
FILE *inp,
*outp;

int number;
int input_status;
int finish;

inp = fopen("prime.dat","r");
outp = fopen("prime.out","w");

input_status = fscanf ( inp, "%d", &number);

finish = number;

while (input_status == 1){
if (is_prime(number))
fprintf(outp, " %d is a prime number\n",number);
else
fprintf(outp, " %d is not a prime number\n",number);

input_status = fscanf ( inp, "%d", &number);

}

fclose(inp); /* close files */
fclose(outp);
return(0);

}

int is_prime(int num)
{
int div;
int all_div;
int result;

if (num == 1)
return(FALSE);
else if (num == 2)
return(TRUE);

all_div = sqrt((double)num);

for(div = 2; div <= all_div; div++)
{
if(num % all_div == 0)
result = FALSE;
else
result = TRUE;
}
return(result);

}

For some reason, I am not getting correct calculations.
Here is what I get when I run it.

50 is a prime number
17 is a prime number
45 is a prime number
19 is a prime number
2 is a prime number
36 is not a prime number
31 is a prime number
41 is a prime number
52 is a prime number
80 is not a prime number
84 is a prime number
65 is a prime number
61 is a prime number
63 is not a prime number
77 is a prime number

Thanks
• 10-20-2005
In the IsPrime() function, all_div is wrong.

Change
Code:

all_div = sqrt((double)num);
to
Code:

all_div = num/2;
• 10-20-2005
1rwhites
Here is my data now.
50 is not a prime number
17 is a prime number
45 is a prime number
19 is a prime number
2 is a prime number
36 is not a prime number
31 is a prime number
41 is a prime number
52 is not a prime number
80 is not a prime number
84 is not a prime number
65 is a prime number
61 is a prime number
63 is a prime number
77 is a prime number

I'm still getting some wrong data. Any other suggestions?

The way it is right now, it says every even number is not prime and every odd number is prime. But I don't know how to fix that.
• 10-20-2005
quzah
No, actually using the square root is "more correct". Once you've hit the square root of a number, there's no point in going any higher, because you've already done those. Consider:

1x8
2x4
(square root hits here)
4x2
8x1

The square root check hits before you reach the half way point. This is just a simple illustration, but the point is, the square root of a number will be less than half of a number, and there's no point in checking any further.

Back to the loop...

Anything divisible by 2 is not a square root, so that elminates half of the numbers you'd check. Increment by 2 then, instead of 1. That saves you half the needed calculations.

Quzah.
• 10-20-2005
if(num % all_div == 0)
result = FALSE;

This should be

if(num % div == 0)
result = FALSE;
• 10-21-2005
shyam168
Solution : Prime Number
Hi ,

Gone thru your code...... A small change is required as follows

1) Change the following if loop (result = FALSE) part
Code:

if(num % all_div == 0)  to

if(num % div == 0)
{
result = FALSE;
break;
}

2) Change the line
Code:

all_div = sqrt((double)num);    to

all_div = (int)sqrt((double)num);

It should work....

Have a nice day
• 10-21-2005
Salem
It's not like googling "prime number algorithm" returns 0 results or anything.
• 10-21-2005
1rwhites
OK here is my code now.

Code:

#include <stdio.h> /* define fopen,fclose,fscanf,fprintf */
#include <math.h> /* sqrt definition */
#define TRUE 1
#define FALSE 0

int is_prime(int num);

int main(void)
{
FILE *inp,
*outp;

int number;
int input_status;
int finish;

inp = fopen("prime.dat","r");
outp = fopen("prime.out","w");

input_status = fscanf ( inp, "%d", &number);

finish = number;

while (input_status == 1){
if (is_prime(number))
fprintf(outp, " %d is a prime number\n",number);
else
fprintf(outp, " %d is not a prime number\n",number);

input_status = fscanf ( inp, "%d", &number);

}

fclose(inp); /* close files */
fclose(outp);
return(0);

}

int is_prime(int num)
{
int div;
int all_div;
int result;

if (num == 1)
return(FALSE);
else if (num == 2)
return(TRUE);

all_div = (int)sqrt((double)num);

for(div = 2; div <= all_div; div++)
{
if(num % div == 0)
result = FALSE;
else
result = TRUE;
}
return(result);

}

but i'm still getting this as my data

50 is a prime number
17 is a prime number
45 is a prime number
19 is a prime number
2 is a prime number
36 is not a prime number
31 is a prime number
41 is a prime number
52 is a prime number
80 is not a prime number
84 is a prime number
65 is a prime number
61 is a prime number
63 is not a prime number
77 is a prime number
• 10-21-2005
Salem
if(num % div == 0)
result = FALSE;
else
result = TRUE;
You've got to check all the numbers before finally returning TRUE.
Any false is immediate exit from the function.
You only get true if ALL the tests fail
• 10-21-2005
1rwhites
Ok everything is good. thanks everyone for your help.