Number of Primes in Range

Pages: 12
closed account (oG8qGNh0)
Write a program that asks the user for two non-negative integers and then displays a message indicating the number of primes found between the two numbers entered by the user (including those two numbers).

You will count the original numbers in your consideration.

You may assume the following: first number < second number.

A prime number is an integer that has no factors other than one and itself.

Output should look similar to:

Enter starting number: 50
Enter ending number: 59
Number of primes in range: 2

Hint: You cannot determine that a number is prime until you have evaluated all the potential factors, but the moment you find a factor, you can say, for certain, that it is NOT prime.

My program:

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
33
34
35
36
37
38
39
 
#include <iostream>
using namespace std; 
  
int main() 
{ 
 
int a, b, i, j, flag;
 
cout << "Enter starting number: "; 
cin >> a; 
  
cout << "Enter ending number: "; 
cin >> b;  
  
cout << "Numbers of prime in range: "
<< a << " and " << b << " are: "; 
  

for (i = a; i <= b; i++) { 
   
if (i == 1 || i == 0) 
continue; 
  
      
flag = 1; 
  
for (j = 2; j <= i / 2; ++j) { 
if (i % j == 0) { 
flag = 0; 
break; 
} 
} 
  
        
if (flag == 1) 
cout << i << " "; 
} 
return 0; 
}


When it says "Number of primes in range:" The output does not give how many numbers there are between the 2, it just gives the numbers. For ex. If I enter 50 and 59, the output doesnt give "Number of primes in range: 2" it gives "Number of primes in range: 53 and 59. How would I change it so it would look like "Number of primes in range: 2"
Last edited on
Repeater (3046)
Your code does not appear to do any actual counting of primes.

You need to examine every number between a and b, and count the ones that are prime, and output that value.
closed account (oG8qGNh0)
my teacher said it should look SIMILAR to

Enter starting number: 50
Enter ending number: 59
Number of primes in range: 2

Wouldn't it be similar?

My output is

Enter starting number: 50
Enter ending number: 59
Number of primes in range: 50 and 59 are: 53 59
Repeater (3046)
When flag == 1, don't output the number. Increment a count.

Then when finished, output that count.
closed account (oG8qGNh0)
What do you mean by increment a count?
ne555 (10692)
1
2
3
4
 
count = 0
for number in range(low, high):
   if is_prime?(number):
      count += 1
closed account (oG8qGNh0)
and replace with

1
2
3
4
 
flag = 1;  
for (j = 2; j <= i / 2; ++j) { 
if (i % j == 0) { 
flag = 0;

????
Repeater (3046)
1
2
3
 
if (flag == 1) 
cout << i << " ";  // DON'T DO THIS. INSTEAD, INCREMENT A COUNT
}
closed account (oG8qGNh0)
1
2
3
4
 
count = 0
for number in range(low, high):
   if is_prime?(number):
      count += 1


number in line 2 is underlined
Repeater (3046)
That would be because you don't appear to be writing C++ code . ne555 wrote something that explained to you what to do. You still have to write the code yourself.
Last edited on
seeplus (6592)
1
2
3
4
5
6
 
for (j = 2; j <= i / 2; ++j) { 
    if (i % j == 0) { 
        flag = 0; 
        break; 
    } 
}


This is very inefficient. The terminating condition can be j * j <= i. Also, if a number (except 2) is divisible by 2, then it is not prime. If this test is done outside of the loop, then j can start at 3 and be incremented by 2.

closed account (oG8qGNh0)
!
Last edited on
closed account (oG8qGNh0)
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
 
#include <iostream>
#include<math.h>
using namespace std;
int main()
{
int num1,num2;
int fnd = 0,ctr = 0;
cout << "Enter starting number: ";
cin >> num1;
cout << "\nEnter ending number: ";
cin >> num2;		

cout << "\nThe prime numbers between " << num1 << " and " << num2 <<" are: "<<endl;
for(int i = num1; i <= num2; i++)
{
for(int j = 2; j <= sqrt (i); j++)
{
if(i%j == 0)
ctr++;
}
if(ctr == 0 &&i!= 1)
{ 
fnd++;
cout << i << " ";
ctr  = 0;
}
ctr = 0;
}
cout << "\n\nNumbers of prime in range " << num1 << " to " << num2 <<" is: " << fnd << endl;
return 1;
}


I am done with the code... How would you have done it?
Last edited on
seeplus (6592)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

int main()
{
	int num1, num2;

	cout << "Enter starting number: ";
	cin >> num1;

	cout << "\nEnter ending number: ";
	cin >> num2;

	int ctr {(num1 = num1 < 1 ? 1 : num1) < 3};

	for (int i = max(3, num1 + !(num1 % 2)), got; got = true, i <= num2; ctr += got, i += 2)
		for (int j = 3, k = static_cast<int>(sqrt(i)); got && j <= k; got = (i % j) != 0, j += 2);

	cout << "\n\nNumber of primes in range " << num1 << " to " << num2 << " is: " << ctr << endl;
}


The only even prime is 2. The others are all odd. An odd number is not prime if divisible by an odd number (actually not prime if divisible by another prime). If the starting number is odd, then the outer loop can inc by 2 rather than 1. If we only test odd numbers, then the inner loop can start at 3 and inc by 2. So first make num1 odd. IF num1 < 3 then start at 3 and init ctr to 1 rather than 0. sqrt() is an 'expensive' function (takes time to execute). It's therefore better to calculate this value once within the i loop - rather than every time through the loop. As the only stipulation is that first < second and prime numbers are all positive, need to deal with num1 being negative.


Last edited on
seeplus (6592)
For the difference in performance between the 2 codes, see https://repl.it/repls/NoisyPurpleQbasic#main.cpp

For the number of primes in the range 1 - 900,000, both versions produce the same result (71274).

However, whereas my code takes 537ms (approx 1/2 second), naveenmmenon code takes 34,056 ms (approx 34 seconds)!
lastchance (6980)
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
 
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <chrono>
#include <vector>
#include <numeric>
using namespace std;


bool isOddPrime( int n )                    // Call for n odd and n > 2 only
{
// if ( n < 2      ) return false;          // Reinstate if conditions above not guaranteed
// if ( n % 2 == 0 ) return n == 2;         //

   int imax = sqrt( n + 0.5 );              // "+ 0.5" = paranoia
   for ( int i = 3; i <= imax; i += 2 )
   {
      if ( n % i == 0 ) return false;
   }
   return true;
}


int countPrimes( int n1, int n2 )           // Count primes between n1 and n2
{
   int counter = ( n1 <= 2 && n2 >= 2 );    // Only even prime is 2
   n1 = max( n1 + 1 - n1 % 2, 3 );          // Odd number greater than or equal to 3
   for ( int n = n1; n <= n2; n += 2 ) counter += isOddPrime( n );
   return counter;
}


int sieve( int N )                          // Sieve of Eratosthenes
{
   vector<bool> prime( N + 1, true );
   prime[0] = prime[1] = false;

   int imax = sqrt( N + 0.5 );
   for ( int i = 2; i <= imax; i++ )
   {
      if ( prime[i] )
      {
         for ( int j = i * i; j <= N; j += i ) prime[j] = false;
      }
   }

   return accumulate( prime.begin(), prime.end(), 0 );
}

int main()
{
   int n1 = 1, n2 = 900000;
   auto t1 = chrono::high_resolution_clock::now();
   int numSearch = countPrimes( n1, n2 );
   auto t2 = chrono::high_resolution_clock::now();
   int numSieve  = sieve( n2 );
   auto t3 = chrono::high_resolution_clock::now();

   cout << "Number of primes between " << n1 << " and " << n2 << " by search: " << numSearch << '\n';
   cout << "Number of primes between " <<  1 << " and " << n2 << " by sieve:  " << numSieve  << '\n';
   cout << "Time taken for search = " << chrono::duration<double,milli>( t2 - t1 ).count() << " ms\n";
   cout << "Time taken for sieve  = " << chrono::duration<double,milli>( t3 - t2 ).count() << " ms\n";
}


Number of primes between 1 and 900000 by search: 71274
Number of primes between 1 and 900000 by sieve:  71274
Time taken for search = 127.91 ms
Time taken for sieve  = 4.37913 ms
Last edited on
seeplus (6592)
Using the same compiler (https://repl.it/repls/CompetitivePitifulVariables#main.cpp)


Number of primes between 1 and 900000 by search: 71274
Number of primes between 1 and 900000 by sieve:  71274
Time taken for search = 395.692 ms
Time taken for sieve  = 175.643 ms


:) :)
lastchance (6980)
Try cpp.sh
Which is where my timing came from. I don't think repl.it has much optimisation.

You could also try
https://rextester.com/PSZY58995



You can make the sieve go about 25% faster by dealing with 2 as a special case first, then incrementing i by 2 each time and j by 2i each time to stay within odd numbers. Or you could just mark odd numbers only. However, it makes a mess of the simplicity of the sieve.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
int sieve( int N )                          // Sieve of Eratosthenes
{
   vector<bool> prime( N + 1, true );
   prime[0] = prime[1] = false;

   int imax = sqrt( N + 0.5 );
   for ( int j = 4; j <= N; j += 2 ) prime[j] = false;                 // Special case for evens
   for ( int i = 3; i <= imax; i += 2 )                                // Step through odds only
   {
      if ( prime[i] )
      {
         for ( int j = i * i; j <= N; j += 2 * i ) prime[j] = false;   // Steps in 2i
      }
   }

   return accumulate( prime.begin(), prime.end(), 0 );
}
Last edited on
seeplus (6592)
I don't think repl.it has much optimisation.


It uses clang. I used repl.it because that is what naveenmmenon uses.

For comparison, the timing for the revised sieve is:


Time taken for sieve  = 115.559 ms

Last edited on
closed account (oG8qGNh0)
Do you also use repl.it? If not what do you use to code?
Pages: 12