Thread: algorithm

  1. #1
    Unregistered
    Guest

    algorithm

    I am making a prime number geneerator. The way I am doing it is by incrementing the number and using if statements to filter out the numbers that arent prime. Is there an algorithm to check and see if a number is even, since there are no even primes.

  2. #2
    Unregistered
    Guest
    nm i use this

    if (i%2 != 0)

  3. #3
    Unregistered
    Guest
    ok. Now I need to eliminate all multiples of 3, anyone have an idea on how to do that?

  4. #4
    Unregistered
    Guest
    ok i got it. Here is my code. There are only a few little problems in it. Say the user enters 100, the prime numbers stop at 100, but i want 100 primes printed. It also prints 1.

    Code:
    /**************************************************
    Filename: pgen.c 
    Author: Mike Hartwig 
    Purpouse: Generate given amount of prime numbers. 
    Input: Keyboard 
    Output: Screen 
    ***************************************************/ 
    #include <stdio.h> 
    #include <stdlib.h> 
    
    int main () 
    { 
    	int prime_amount; //the amount of primes to generate. 
    	int prime_count = 1;  
    	int prime_answer; // the answer. 
    	
    	printf("Welcome to the Prime Number Generator.\n"); 
    	printf("How many prime numbers would you like to generate: "); 
    	scanf("%d", &prime_amount); 
    	printf("Generating %d prime numbers...\n", 
    	prime_amount); 
    	printf("2, 3, 5, 7 ");
    		do 
    			{ 
    			prime_answer = prime_count++; 
    
    				if(prime_answer % 2 != 0 && prime_answer % 3 != 0 && prime_answer % 5 != 0 && prime_answer % 7 != 0)
    					{
    					printf("%d, ", prime_answer);
    					}
    			}
    		while (prime_count < prime_amount); 
    
    return (0); 
    }

  5. #5
    train spotter
    Join Date
    Aug 2001
    Location
    near a computer
    Posts
    3,868
    Why not
    Code:
    int  FindPrime(int iNumberToTest)
    {
    int  iTemp;
    
    //as far as I am concerned 1 is not prime as it 
    //has no numbers less than it that it is not divisible by
        if(iNumberToTest==1) return FALSE; 
        for(iTemp=2;iTemp<iNumberToTest;iTemp++)// could even use iNumberToTest/2
        {
            if(iNumberToTest%iTemp==0)
                 return FALSE;
        }
        return TRUE;
    }
    Put that in a while loop, incrementing the number to test until the required amount of primes found.
    Last edited by novacain; 03-01-2002 at 01:34 AM.
    "Man alone suffers so excruciatingly in the world that he was compelled to invent laughter."
    Friedrich Nietzsche

    "I spent a lot of my money on booze, birds and fast cars......the rest I squandered."
    George Best

    "If you are going through hell....keep going."
    Winston Churchill

  6. #6
    Unregistered
    Guest
    oh here is what i have now.

    Code:
    /**************************************************
    Filename: main.c 
    Author: Mike Hartwig 
    Purpouse: Generate given amount of prime numbers. 
    Input: Keyboard 
    Output: Screen 
    ***************************************************/ 
    #include <stdio.h> 
    #include <stdlib.h> 
    #include <math.h>
    
    int main () 
    { 
    	int prime_amount; //the amount of primes to generate. 
    	int prime_count = 3;  
    	int prime_answer; // the answer. 
    	
    	printf("Welcome to the Prime Number Generator.\n"); 
    	printf("How many prime numbers would you like to generate: "); 
    	scanf("%d", &prime_amount); 
    		if (prime_amount < 0) //dont print any primes if given amount is less than 0
    			{
    			printf("Please Enter A Number Greater Than 0\n");
    			}
    		else
    			{
    			printf("Generating %d prime numbers...\n", prime_amount); 
    			}
    		do 
    			{ 
    			prime_answer = prime_count++; 
    				
    				if (prime_answer == 2)
    					{
    					printf("2 ");
    					}
    				
    				if (prime_answer == 3)
    					{
    					printf("3 ");
    					}
    				
    				if (prime_answer == 5)
    					{
    					printf("5 ");
    					}
    				
    				if (prime_answer == 7)
    					{
    					printf("7 ");
    					}
    
    				if (prime_answer % 2 != 0 && prime_answer % 3 != 0 && prime_answer % 5 != 0 && prime_answer % 7 != 0)
    					{
    					printf("%d ", prime_answer);
    					}
    			}
    		while (prime_count <= prime_amount); 
    	
    return (0); //done
    }
    You can go ahead and compile it. The only problem is it should generate the given amount of prime numbers, not print prime numbers till it gets to the given amount.

    Say you want to print 100 prime numers, mine only prints until it hits the number 97. It should print 100 prime numbers.

  7. #7
    Unregistered
    Guest

    Talking

    plz i need some help...

  8. #8
    Unregistered
    Guest
    for this if statement:

    Code:
    if (prime_answer % 2 != 0 && prime_answer % 3 != 0 && prime_answer % 5 != 0 && prime_answer % 7 != 0)
    					{
    					printf("%d \n", prime_answer);
    					}
    Is there a way I can exclude 2, 3, 5, and 7 from this, so they get counted for prime_amount?

  9. #9
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <math.h>
    
    #define MAX_NR_PRIMES 100000
    
    int main(int argc, char* argv[])
    {
        int nr_primes;
        int* primes_found;
        int nr_found = 0;
        int i, n = 3;
        int prime;
        int check;
    
        if (argc < 2) {
            fprintf(stderr, "Usage: prime [NUMBER_OF_PRIMES]\n");
            return EXIT_FAILURE;
        }
    
        nr_primes = atoi(argv[1]);
        if (nr_primes < 0 || nr_primes > MAX_NR_PRIMES) {
            fprintf(stderr, "Invalid usage\n");
            return EXIT_FAILURE;
        }
    
        primes_found = malloc(nr_primes * sizeof(int));
        if (primes_found == NULL) {
            fprintf(stderr, "prime: Ran out of memory\n");
            return EXIT_FAILURE;
        }
    
        primes_found[nr_found++] = 2;
        while(nr_found != nr_primes) {
            prime = 1;
    
            check = sqrt(nr_found);
            for (i = 0; prime && i < check; ++i) {
                if (n % primes_found[i] == 0)
                    prime = 0;
            }
            if (prime) 
                primes_found[nr_found++] = n;
            n += 2;
        }
    
        for (i = 0; i < nr_found; ++i) {
            printf("%-5d ", primes_found[i]);
            if ((i + 1) % 13 == 0)
                putchar('\n');
        }
        putchar('\n');
    
        free(primes_found);
        
        return 0;
    }

  10. #10
    Registered User
    Join Date
    Oct 2001
    Posts
    197
    Here is some really efficient code from the book "Algorithms in C" (I translated the name from German into English, maybe the book´s name is a little different!):
    Code:
    #define N 100000
    
    int main(void)
    {
      char p[N];
      register unsigned long i;
      unsigned long j;
    
      for(i=1;i<N;p[i]=1, i+=2) ;
    
      for(i=2, p[1]=0;j<N/2;i++)
          if p[i] for(j=2;j<N/i;j++) p[i*j]=0;
    
      for(i=1;i<MAX;i+=2)
           if p[i] printf("%lu\n", i);
    
      return 0;
    }
    I hope it´s correct. I tried to optimize it a little...

    klausi
    Last edited by klausi; 03-03-2002 at 11:23 AM.
    When I close my eyes nobody can see me...

  11. #11
    train spotter
    Join Date
    Aug 2001
    Location
    near a computer
    Posts
    3,868
    Unreg,
    Don't take this the wrong way, I am trying to help. Your approach is incorrect.

    You are not thinking general enough. You can write a very long IF() statement but this is not the correct answer. Doing that will not improve your programming. If you need to find 1,000,000 primes it is impossible to write your kind of program. Do not be limited by the scope of the question and look beyond. If you write a good small piece of code it can always be used in a bigger / another program later.

    Every answer here is a different approach to the same problem, all seem valid. (though I think I see some minor errors in Klausi's with the char array acting like an int array at points)

    The difference is they will work if any number of primes are requested.

    Have you learnt functions?
    (breaking a progam up into small blocks or 'functions'. A block can be called more than once making for shorter code)
    Arrays?
    (a number or group of like variables)
    Code:
    FIND PRIMES
    Ask user for number of primes to find (validate)
    while(Primes Found<Primes Needed)
    {
         test number for 'primeness'
         if(is prime)
         {
              print to screen
              increase number primes found
         }
         increase number to test
    }//or [do while] is as good/better
    exit
    "Man alone suffers so excruciatingly in the world that he was compelled to invent laughter."
    Friedrich Nietzsche

    "I spent a lot of my money on booze, birds and fast cars......the rest I squandered."
    George Best

    "If you are going through hell....keep going."
    Winston Churchill

  12. #12
    Registered User
    Join Date
    Oct 2001
    Posts
    197
    @novacain:
    I took a char array for saving memory. Why should I use an integer, which is at least two times bigger than a char, for a simple flag?

    klausi
    When I close my eyes nobody can see me...

  13. #13
    Registered User dharh's Avatar
    Join Date
    Jan 2002
    Posts
    51

    redone klausi's code

    just fixed some stuff

    Code:
    #include <stdio.h>
    
    #define N 100000
    #define MAX 20  /* number of primes you want */
    
    int main(void) {
      char p[N];
      register unsigned long i;
      unsigned long j;
    
      for(i=1;i<N;p[i]=1, i+=2) ;
    
      for(i=2, p[1]=0;j<N/2;i++)
          if(p[i]) for(j=2;j<N/i;j++) p[i*j]=0;
    
      for(i=1;i<MAX;i+=2)
           if(p[i]) printf("%lu\n", i);
    
      return 0;
    }

  14. #14
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    I didn't look through your code in detail, but it looks like you increase the counter in you for-loop with 1 per step. Since all even numbers are NOT prime numbers, you can increase with 2 per step instead, so you check these numbers:

    1,3,5,7,9,11...

    instead of:

    1,2,3,4,5...
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  15. #15
    Registered User
    Join Date
    Feb 2002
    Posts
    589
    How about doing it something like this?

    Code:
    #include <stdio.h>
    #include <time.h>
    #include <math.h>
       
    int prime(int num);/*Returns 1 if num is a prime, 0 if not*/
      
    int main (void)
    {
       int tested_number = 2;/*Number currently tested*/
       int upper_limit = 10000;/*Max number to test*/
       double start;
       double finish;
       
       printf("***********************************************\n");
       printf("*                                                       *\n");
       printf("* Welcome to the program that finds prime numbers.      *\n");
       printf("* Current settings gives the numbers between %d and %d  *\n",tested_number, upper_limit);
       printf("*                                                       *\n");
       printf("*********************************************\n\n");
       
       start = clock(); /*Set start*/
       
       while(tested_number < upper_limit)/*Counts between tested_number and upper_limit-1*/
       {
           if(prime(tested_number))/*Calls prime() wish returns 1 if tested_number is a prime*/
           {
               printf("%d\n",tested_number);
           }
           tested_number++;
       }
       
       finish = clock();/*Set finish*/
       
       /*prints time it toke to calculate prime numbers*/
       printf("Task finished in %2.3f seconds\n", (finish - start) / CLOCKS_PER_SEC  );
       
       return 0;/* Tell the operating system we did OK */
       }
       
       
       int prime(int num)
       {
          double max_to_test = sqrt(num);/*Defines the upper limit that needs to be tested*/
          int counter = 2;/*Defines the lover limit that needs to be tested*/
          int is_a_prime = 1;/*Return value that get changed to 0 if tested number is not a prime*/
       
          while(counter <= max_to_test)/*Count between lower limit and upper limit*/
          {
              if(num % counter == 0)/*If this is true it is not a prime*/
       	  {
       	     is_a_prime = 0;/*Return 0*/
              }
              counter++;
          }
          return is_a_prime;
       }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Implement of a Fast Time Series Evaluation Algorithm
    By BiGreat in forum C Programming
    Replies: 7
    Last Post: 12-04-2007, 02:30 AM
  2. Replies: 4
    Last Post: 12-10-2006, 07:08 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM