Thread: Prime numbers

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

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

Originally Posted by slingerland3g

Food for thought

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

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

--
Mats

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.

Originally Posted by slingerland3g

Food for thought

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

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

Originally Posted by 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.

Yeah I know it's very trivial.
Anyway would you mind posting your efficient implementation?

Originally Posted by slingerland3g

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

You mean "kudos"...

QuantumPete

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

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.

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.

Originally Posted by slingerland3g

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!