Prime numbers

[Imbellis]

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.

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

[zacs7]

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;

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

[matsp]

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

[slingerland3g]

Food for thought

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

[matsp]

Food for thought

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Yes. That's a clever algorithm but slightly more complex to implement.

--
Mats

[stevesmithx]

Food for thought

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

I just tried that one.
Here's my naive implementation.

//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;
}

[abachler]

// 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.

[grumpy]

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).

[abachler]

int64 is an ansi standard datatype. __int64 is the windows specific implimentation of that datatype. The code is only trivially windows dependant, i.e. change the datatype from __int64 to int64 and it is ansi standard.

The code gains a huge performance increase in teh root optimization versus calculating teh root every iteration. Converting the relatively slow sqrt() to a simple divide and compare. As for the value of using SoE versus checking all odd numbers it depends on several factors, but mostly the speed of performign the calculations entirely in registers and the L1 cache versus making frequent calls into L2 and eventually uncached memory. Once the primes you are testing exceed available L2 memory for storage of the divisors, you will essentialyl be runnign at teh speed fo primary memory, which is usually orders of magnitude slower than my code, which will always run at synchronous speeds. Aside from that this code is designed to illustrate a solution not to be entered into the hall of fame for most optimized code EVAR.

[matsp]

int64 is an ansi standard datatype. __int64 is the windows specific implimentation of that datatype. The code is only trivially windows dependant, i.e. change the datatype from __int64 to int64 and it is ansi standard.

The code gains a huge performance increase in teh root optimization versus calculating teh root every iteration. Converting the relatively slow sqrt() to a simple divide and compare. As for the value of using SoE versus checking all odd numbers it depends on several factors, but mostly the speed of performign the calculations entirely in registers and the L1 cache versus making frequent calls into L2 and eventually uncached memory. Once the primes you are testing exceed available L2 memory for storage of the divisors, you will essentialyl be runnign at teh speed fo primary memory, which is usually orders of magnitude slower than my code, which will always run at synchronous speeds. Aside from that this code is designed to illustrate a solution not to be entered into the hall of fame for most optimized code EVAR.

However, the many of the non-primes are divisible by small numbers, so it will be only be on a few of them that you go all the way to the square root of the number.

A 512KB cache will hold 128K primes. If we roughly say that primes are 300 per 1000 numbers, then there is about 360K primes that fits in the cache.

--
Mats

[abachler]

there are approximately x/ln(x) prime numbers smaller than x. That is very innacurate at low values of X but gradually becomes more accurate and eventually underestimates by a small percentage.

But as I stated, the code i posted was intended to illustrate a solution not as the most optimized solution. It is an EXAMPLE.

If you want we can have a contest to see who can generate the fastest prime generator, Ill post it in teh contests channel.

[grumpy]

int64 is an ansi standard datatype. __int64 is the windows specific implimentation of that datatype. The code is only trivially windows dependant, i.e. change the datatype from __int64 to int64 and it is ansi standard.

Not true. int64 is not a standard type in either C or C++.

The code gains a huge performance increase in teh root optimization versus calculating teh root every iteration. Converting the relatively slow sqrt() to a simple divide and compare.

You have some measurements to back that up? Having a loop that does divide-and-compares on most iterations will fairly quickly exceed the time for computing a square root: division is also a relatively expensive operation. Of course, computing sqrt() has other tradeoffs (most notably that there is no guarantee that the double type will hold larger integral values) but that's another story - I wouldn't use sqrt() with the SoE either.

As for the value of using SoE versus checking all odd numbers it depends on several factors, but mostly the speed of performign the calculations entirely in registers and the L1 cache versus making frequent calls into L2 and eventually uncached memory. Once the primes you are testing exceed available L2 memory for storage of the divisors, you will essentialyl be runnign at teh speed fo primary memory, which is usually orders of magnitude slower than my code, which will always run at synchronous speeds.

I'm not saying you're wrong here, but I'd be interested in seeing measurements to back up your comments. Relying on L1 and L2 cache hits is highly system dependent, highly dependent on how your compiler and system optimises operations. However, increasing the rates of cache hits does not change the fact that your code inherently does more expensive operations (notably division) than alternate approaches like SoE. I'd be interested to know where the cross-over point is.

Your comments on relative performance with SoE are easy to justify for small primes, but harder to justify for larger ones (as, when testing a large value, there are more divisors to be eliminated, and therefore more divisions to be performed).

[abachler]

Not true. int64 is not a standard type in either C or C++.

The Long Long Int Types (C Only)

64 bit processors have been readily available in workstations for several years, and they will be coming to desktop computers soon. These processors can address enough memory to have arrays with more elements than a 32 bit long can specify. Inexpensive disk drives in use today can hold a file which contains more bytes than a 32 bit offset can reach. The requirement for an integer type required to hold more than 32 bits is obvious.

The 1999 update to the ANSI/ISO C language standard has added a new integer type to C, one that is required to be at contain at least 64 bits. Included in this update are the new variable types signed and unsigned long long . The selected name comes from gcc and several other compilers which already provide this type as an extension. On 32 bit Windows compilers from Microsoft, Borland (and maybe others) this same extension has the name __int64.

You have some measurements to back that up? Having a loop that does divide-and-compares on most iterations will fairly quickly exceed the time for computing a square root: division is also a relatively expensive operation. Of course, computing sqrt() has other tradeoffs (most notably that there is no guarantee that the double type will hold larger integral values) but that's another story - I wouldn't use sqrt() with the SoE either.

it divide and compares once per loop versus sqrt() once per loop, therefore its a one to one comparison. sqrt() is slower than divide and compare.

I'm not saying you're wrong here, but I'd be interested in seeing measurements to back up your comments. Relying on L1 and L2 cache hits is highly system dependent, highly dependent on how your compiler and system optimises operations. However, increasing the rates of cache hits does not change the fact that your code inherently does more expensive operations (notably division) than alternate approaches like SoE. I'd be interested to know where the cross-over point is.

Your comments on relative performance with SoE are easy to justify for small primes, but harder to justify for larger ones (as, when testing a large value, there are more divisors to be eliminated, and therefore more divisions to be performed).

By all means, post your SoE implimentation on the contest.

[slingerland3g]

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.

[stevesmithx]

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?