Algorithm to find prime numbers in a range

Jun 25, 2015 at 8:02am
Hi. Say I wish to find all the prime numbers between 10 to 50

What is the algorithm for this?

Thanks
Jun 25, 2015 at 8:43am
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
Jun 25, 2015 at 9:21am
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.
Jun 25, 2015 at 6:24pm
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
Last edited on Jun 28, 2015 at 10:37pm
Jun 25, 2015 at 8:50pm
You only have to test for division by all the prime numbers less or equal than sqrt(itself)
Jun 25, 2015 at 9:19pm
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.
Last edited on Jun 25, 2015 at 9:20pm
Jun 26, 2015 at 7:15am
thanks all, I try it
Jun 27, 2015 at 3:57pm
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#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
Jun 28, 2015 at 2:26am
@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 N2 , 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

Topic archived. No new replies allowed.