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?

Thanks in advance.

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.

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

Can someone please help me with what I'm doing wrong?

Thanks

In the IsPrime() function, all_div is wrong.

Change

Code:

---

all_div = sqrt((double)num);

---

to

Code:

---

all_div = num/2;

---

That will fix your problem.

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.

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.

if(num % all_div == 0)
result = FALSE;

This should be

if(num % div == 0)
result = FALSE;

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

It's not like googling "prime number algorithm" returns 0 results or anything.

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

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

Ok everything is good. thanks everyone for your help.