Prime numbers

This is a discussion on Prime numbers within the C Programming forums, part of the General Programming Boards category; Hi there. I've been asked to make a programme that finds and prints prime numbers. To do this, I set ...

  1. #1
    Registered User
    Join Date
    Nov 2008
    Posts
    1

    Prime numbers

    Hi there. I've been asked to make a programme that finds and prints prime numbers. To do this, I set up a simple for loop that tests if the number can be divided by even or odd numbers.

    Code:
    int main (void) {
       
       int i=0;
       int r=0;
       int numstatus1;
       int numstatus2;
       int status=0;
       char line[100];
       
       while(1) {
            printf("Enter maximum number to count prime numbers to:\n");
    		fgets(line, sizeof(line), stdin);
            status=sscanf(line, "%d", &r);
            if (status==0) printf("Invalid number.\n");
    		else break;
    		}
    		
    		for (i=0; i<r; i++) {
    		 numstatus1=0;
    		 numstatus2=0;
    		
    		   numstatus1=i/2;
    		   numstatus2=i/3;   
               if ??? printf("%d is prime", i);
    		   }
        return 0;
    }
    I've now got stuck on the very simple problem that I can't make it actually print the numbers that satisfy my conditions. This is probly a really stupid problem but its been bugging me!

    Thanks in advance

  2. #2
    Woof, woof! zacs7's Avatar
    Join Date
    Mar 2007
    Location
    Australia
    Posts
    3,459
    The definition of a prime number should be enough, but...

    Your current method will not work, who cares if it's divisible by even or odd numbers? That really has nothing to do with it **

    ** Unless you're doing some sort of optimization.

    Basically, you need to: print any number that is not divisible by 2 to sqrt(r), ranging from 1 to r as you're almost doing (don't go from 0, or 1 even). You could consider this in PDL;

    Code:
    integer r = <user input>
    integer i = 0;
    integer n = 0;
    
    // Test all numbers upto r, we'll say 1 is NOT a prime
    for(i = 2; i < r; i++)
    {
       boolean isPrime = true;    // assume prime
       integer range = square_root(i);
       // check if i is divisible by n
       for(n = 2; n < range; n++)
       {
          if((i modulus n) == 0)
          {
              isPrime = false;
              break;
          }
       }
    
       // print i, because it's prime
       if(isPrime)
          print i
    }
    Or something like that, you'll notice it's not C

  3. #3
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Right, so the "correct" solution would be to divide, and see if there is a remainder - use the modulo operator (%) to find the remainder [1] - by all primes up to SQRT(x)+1, where x is the "may be a prime" number.

    A method that doesn't involve knowing which primes there are to know if this is a prime would be to check the remainder for 2 and then all odd numbers (3, 5, 7, ...) up to the square root of x. If you move the 2 check out of the loop, then it's a simple exercise to form a loop that checks all the odd values.

    Use a separate "flag" variable to indicate if any of the tests failed (if so, you can quit checking, because it is not a prime).

    After the loop, check the flag and print the appropriate message.

    [1] Technically remainder and modulo are subtly different - but for the purposes here it's not important.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  4. #4
    Registered User slingerland3g's Avatar
    Join Date
    Jan 2008
    Location
    Seattle
    Posts
    602

  5. #5
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by slingerland3g View Post
    Yes. That's a clever algorithm but slightly more complex to implement.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  6. #6
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    Code:
    // PrimeFinder.cpp : Defines the entry point for the console application.
    //
    #include <stdio.h>
    int main(int argc, char* argv[]){
      unsigned __int64 Prime = 3;
      unsigned __int64 Root = 1;
    
      printf("The following numbers are prime:\n\n&#37;d\n%d\n" , 2 , 3);
     
    prime_start:
      while(Prime < 0xFFFFFFFF){
          Prime += 2;
          while((Prime / Root) > Root) Root++;
     
          for(unsigned __int64 Test = 3;Test <= Root;Test+=2){
              if(Prime % Test == 0) goto prime_start;
              }
          printf("%d\n" , Prime);
          }
    
      return 0;
      }
    This uses several optimizations, namely it skips all even numbers, which cant be prime (except 2), and uses a fast method for finding the Root of the prime.
    Last edited by abachler; 11-26-2008 at 09:20 AM.
    Until you can build a working general purpose reprogrammable computer out of basic components from radio shack, you are not fit to call yourself a programmer in my presence. This is cwhizard, signing off.

  7. #7
    and the hat of copycat stevesmithx's Avatar
    Join Date
    Sep 2007
    Posts
    494
    Quote Originally Posted by slingerland3g View Post
    I just tried that one.
    Here's my naive implementation.
    Code:
    //An Implementation of sieve of Eratosthenes
    #include <stdio.h>
    #include <math.h>
    #define N 300 //Upper Limit
    void applysieve(int numbers[]){
        int prime,i,j,count=0;
        for(i=0;i<(sqrt(N)+1);i++){//Repeat the steps till the number is greater than the square root of the Upper Limit
            if(numbers[i]!=0){     //Not Marked as zero,so prime
                prime=numbers[i];
            }
            else{
                continue;          //Current number is not prime so need not find its multiples
            }
        /*find all the multiples of the current prime*/
            for(j=i+1;j<N-1;j++){  //Repeat the steps for each number identified as prime
                if(numbers[j]&#37;prime==0){ //find the multiples of the current prime
                    numbers[j]=0;  //Mark as zero(Eliminate the multiple)
                }
            }
        }
        /* Print all the numbers that are not marked as zero */
        printf("List of prime numbers\n");
        for(i=0;i<N-1;i++){
            if(numbers[i]!=0){
                count++;
                printf("%d\n",numbers[i]);
            }
        }
        printf("Number of primes between 2 and 300 is %d",count);
    }
    int main(){
        int numbers[N+1],i;
        for(i=0;i<N-1;i++){
            numbers[i]=i+2;
        }
        applysieve(numbers);
        return 0;
    }
    Last edited by stevesmithx; 11-26-2008 at 09:49 AM. Reason: Correct the Comment
    Not everything that can be counted counts, and not everything that counts can be counted
    - Albert Einstein.


    No programming language is perfect. There is not even a single best language; there are only languages well suited or perhaps poorly suited for particular purposes.
    - Herbert Mayer

  8. #8
    Registered User slingerland3g's Avatar
    Join Date
    Jan 2008
    Location
    Seattle
    Posts
    602
    Lol, much of the study of Sieve of Eratosthenes is how to make it fast and space efficient. The trick is to fill an array with 1's only. To save even more space use bits only. I have a working solution that is quite nice but most of the code is not my own. Please review Algorithms in C which mentions this code.

  9. #9
    and the hat of copycat stevesmithx's Avatar
    Join Date
    Sep 2007
    Posts
    494
    Quote Originally Posted by slingerland3g View Post
    Lol, much of the study of Sieve of Eratosthenes is how to make it fast and space efficient. The trick is to fill an array with 1's only. To save even more space use bits only. I have a working solution that is quite nice but most of the code is not my own. Please review Algorithms in C which mentions this code.
    Yeah I know it's very trivial.
    Anyway would you mind posting your efficient implementation?
    Not everything that can be counted counts, and not everything that counts can be counted
    - Albert Einstein.


    No programming language is perfect. There is not even a single best language; there are only languages well suited or perhaps poorly suited for particular purposes.
    - Herbert Mayer

  10. #10
    Registered User slingerland3g's Avatar
    Join Date
    Jan 2008
    Location
    Seattle
    Posts
    602
    Here is the books implementation:

    #include <stdio.h>

    #define N 10000 //Codos to anyone that can explain why 100000 may segfault


    Code:
    main ()
    {
      int i, j, a[N];
    
      for (i = 2; i < N; i++)
        a[i] = 1;
    
      for (i = 2; i < N; i++)
        if (a[i])
          for (j = i; i * j < N; j++)
            a[i * j] = 0;
    
      for (i = 2; i < N; i++)
        if (a[i])
          printf ("&#37;4d ", i);
    
      printf ("\n");
    }

  11. #11
    Technical Lead QuantumPete's Avatar
    Join Date
    Aug 2007
    Location
    London, UK
    Posts
    894
    Quote Originally Posted by slingerland3g View Post
    #define N 10000 //Codos to anyone that can explain why 100000 may segfault
    You mean "kudos"...

    QuantumPete
    "No-one else has reported this problem, you're either crazy or a liar" - Dogbert Technical Support
    "Have you tried turning it off and on again?" - The IT Crowd

  12. #12
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    I would have thought that 100000 would be OK, but a million will seg-fault because you run out of stack. If you make it a global (or static), or dynamically allocate the memory, you can make it muchos bigger.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  13. #13
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,662
    Quote Originally Posted by slingerland3g
    The trick is to fill an array with 1's only.
    I believe that it is typically slightly easier to initialise the array with 0s instead. This would replace the first loop (or memset) in your example.

    Quote Originally Posted by slingerland3g
    Codos to anyone that can explain why 100000 may segfault
    Stack size is rather limited.

    By the way, main() normally returns an int, so state as such.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  14. #14
    and the hat of copycat stevesmithx's Avatar
    Join Date
    Sep 2007
    Posts
    494
    Quote Originally Posted by slingerland3g View Post
    Here is the books implementation:

    #include <stdio.h>

    #define N 10000 //Codos to anyone that can explain why 100000 may segfault


    Code:
    main ()
    {
      int i, j, a[N];
    
      for (i = 2; i < N; i++)
        a[i] = 1;
    
      for (i = 2; i < N; i++)
        if (a[i])
          for (j = i; i * j < N; j++)
            a[i * j] = 0;
    
      for (i = 2; i < N; i++)
        if (a[i])
          printf ("%4d ", i);
    
      printf ("\n");
    }
    Thanks singerland3g.
    Oh my! implicit main!
    Not everything that can be counted counts, and not everything that counts can be counted
    - Albert Einstein.


    No programming language is perfect. There is not even a single best language; there are only languages well suited or perhaps poorly suited for particular purposes.
    - Herbert Mayer

  15. #15
    Registered User
    Join Date
    Jun 2005
    Posts
    6,266
    Quote Originally Posted by abachler View Post
    This uses several optimizations, namely it skips all even numbers, which cant be prime (except 2), and uses a fast method for finding the Root of the prime.
    The code will tend to be slower than the Sieve of Eratosthenes for large primes (as it checks if a value is divisible by every odd value less than its square root). The benefit is that it uses less memory (the SoE relies on keeping track of all primes found for subsequent testing, and they have to be stored somewhere).

    Modifying the value of Root through iteration (as the code does) is not necessarily fast: tracking of the value of Root from one iteration to the next is the optimisation. In comparison with the looping over all odd values, the benefit of that optimisation is minor.

    There is the inconvenient fact that the code is also windows specific (relies on compiler extensions).

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Logical errors with seach function
    By Taka in forum C Programming
    Replies: 4
    Last Post: 09-18-2006, 05:20 AM
  2. Replies: 18
    Last Post: 11-04-2005, 01:41 PM
  3. prime numbers, counters, help!
    By vege^ in forum C++ Programming
    Replies: 1
    Last Post: 03-10-2003, 03:32 PM
  4. Prime numbers
    By Lazy Student in forum C Programming
    Replies: 12
    Last Post: 05-14-2002, 05:53 AM
  5. Homework help
    By Jigsaw in forum C++ Programming
    Replies: 2
    Last Post: 03-06-2002, 04:56 PM

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