Algorithm to find prime numbers in a range

[csstudent123]

Hi. Say I wish to find all the prime numbers between 10 to 50

What is the algorithm for this?

Thanks

[ataik]

define each number with decimal,
divide each number to the numbers between 1 and itself, if the decimal isn't zero for each divison, it is prime number

[shadowmouse]

Either than or make a sieve of eratosthenes and either ignore the bits before the lower number, or adjust where each loop starts when you are cycling through it and settings bits to false.

[andywestken]

divide each number to the numbers between 1 and itself,

You only have to test for division by two and all odd numbers as far as itself/2 sqrt(itself)

Andy

Edit: correct doziness

[ne555]

You only have to test for division by all the prime numbers less or equal than sqrt(itself)

[shadowmouse]

But to do so, you need to find what the prime numbers are. This is what the sieve of eratosthenes is for. What you do, is make a bitset with a length of the highest number you want to check + 1. You set them all to true. Then set the first and second bits to false because 1 and 0 are not a prime. Find the first true bit (2) and set every multiple to false, not including 2 itself (4,6,8 e.t.c). Find the next true bit (in this case 3) and set every bit after it which is a multiple of it to false (6,9,12 e.t.c.). Find the next true bit (5) and so on and so on.

[csstudent123]

thanks all, I try it

[Radar]

#include <iostream>
// note the use of function prototypes

bool isDivisible (int number, int divisor);
bool isPrime (int number);

using namespace std;

int main ()
{
      for ( int i = 0; i < 100; i++ )
      {
            if ( isPrime( i ) )
{
                  cout << i << endl;
            }
} }
bool isPrime (int number)
{
      for ( int i = 2; i < number; i++)
{
            if ( isDivisible( number, i  ) )
{
                  return false;
            }
}
      return true;
}
bool isDivisible (int number, int divisor)
{
      return number % divisor == 0;
}

Literally took this out of one of my ebooks

[TheIdeasMan]

@Radar

The code you found is one of the usual naive implementations of prime number finding, and is very inefficient for larger numbers. Try running it for numbers up to 1 million - see how long it takes :+)

The problems with it are:

It divides by every number less than i, as ne555 pointed out, one only needs to check each prime number less than sqrt(i). So as 1 example you are checking for division by 2, 4 , 6 ,8 ... which is obviously a waste.

It's testing all the numbers less than i, but it is only necessary to go to sqrt(i). So if you went to 1 million, you only need to test up to 1,000.

shadowmouse's algorithm is much better.

Although there is one modification:

If N is the number you want to remove multiples of, first remove N² , all the numbers up to there will be prime (as long as one has worked through the list sequentially to this point), then remove multiples of N from there on.

This is called Euler's algorithm and is detailed on the wiki page, near the end.

@csstudent123
Here is a link to a segmented prime sieve, but note that if you submit this code for your assignment, prepare to get busted by your teacher.

http://primesieve.org/
http://primesieve.org/segmented_sieve.html