for loop to find prime numbers

This is a discussion on for loop to find prime numbers within the C Programming forums, part of the General Programming Boards category; For my program, I need to check whether a number is prime or not. I have to use a for ...

  1. #1
    bignood
    Join Date
    Sep 2005
    Posts
    33

    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.

  2. #2
    Captain - Lover of the C
    Join Date
    May 2005
    Posts
    341
    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.
    Don't quote me on that... ...seriously

  3. #3
    bignood
    Join Date
    Sep 2005
    Posts
    33
    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

  4. #4
    Captain - Lover of the C
    Join Date
    May 2005
    Posts
    341
    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.
    Don't quote me on that... ...seriously

  5. #5
    bignood
    Join Date
    Sep 2005
    Posts
    33
    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.
    Last edited by 1rwhites; 10-20-2005 at 03:58 PM.

  6. #6
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.
    Hope is the first step on the road to disappointment.

  7. #7
    Captain - Lover of the C
    Join Date
    May 2005
    Posts
    341
    if(num % all_div == 0)
    result = FALSE;

    This should be

    if(num % div == 0)
    result = FALSE;
    Don't quote me on that... ...seriously

  8. #8
    ..................
    Join Date
    Oct 2005
    Posts
    11

    Cool 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

  9. #9
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,540
    It's not like googling "prime number algorithm" returns 0 results or anything.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  10. #10
    bignood
    Join Date
    Sep 2005
    Posts
    33
    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

  11. #11
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,540
    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
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  12. #12
    bignood
    Join Date
    Sep 2005
    Posts
    33
    Ok everything is good. thanks everyone for your help.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Prime numbers
    By Imbellis in forum C Programming
    Replies: 25
    Last Post: 11-27-2008, 05:37 AM
  2. Logical errors with seach function
    By Taka in forum C Programming
    Replies: 4
    Last Post: 09-18-2006, 05:20 AM
  3. prime numbers re-posted
    By crypto_quixote in forum C Programming
    Replies: 3
    Last Post: 01-17-2006, 07:44 PM
  4. printing only prime numbers
    By Micko in forum C Programming
    Replies: 30
    Last Post: 06-10-2004, 10:23 PM
  5. Prime Numbers
    By Unregistered in forum C++ Programming
    Replies: 1
    Last Post: 09-24-2001, 07:11 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21