C++

Forum

 
I honestly don't understand this insanely-fast efficient prime

closed account (ShbjNwbp)
I have come across this piece of code and the second method (Efficient Prime) finds insanely fast, even it is much longer than the first version (Classic Prime).

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
 
#include <iostream>
#include <vector>
#include <cmath>
#include <ctime>

using namespace std;

bool isPrime(int a)
{
	int i, k;
	static int N = 0;
	static std::vector<bool> primeData;

	if(a <= 1) return false;
	if(a > N)
	{
		N = a + 10000;
		primeData.resize(N + 1);

		for(i = 0; i <= N; i++) primeData[i] = true;
		for(i = 2; i <= N / 2; i++)
		{
			if(primeData[i] == false) continue;

			k = i + i;
			while(k <= N)
			{
				primeData[k] = false;
				k += i;
			}
		}
	}
	return primeData[a];
}

bool isPrimeClassic(int a)
{
    int N = int(sqrt(a)), i;
    if(a <= 1) return false;
    for(i = 2; i <= N; i++) if(a % i == 0) return false; return true;
}

int main() 
{
    int N, i;
    int count;
    double timeElapsed;
    clock_t start_t, end_t;
	do
	{
	    cout << "Enter a number greater than 1 : "; 
	    if(cin >> N && N >= 2)
	    {
	        cin.ignore();
	        break;
	    }
	} while(true);
	
	cout << endl;
	cout << "Classic prime : ";
	
	count = 0;
	start_t = clock();
	for(i = 2; i <= N; i++) if(isPrimeClassic(i)) count++;
	
	end_t = clock();	
	timeElapsed = (double)(end_t - start_t) / (double)CLOCKS_PER_SEC;
	cout << count << " prime number(s) have been found in " << timeElapsed << " second(s)." << endl;
	
	cout << "Efficient prime : ";
	
	start_t = clock();
	isPrime(N);	
	count = 0;
	for(i = 2; i <= N; i++) if(isPrime(i)) count++;	
	
	end_t = clock();		
	timeElapsed = (double)(end_t - start_t) / (double)CLOCKS_PER_SEC;
	cout << count << " prime number(s) have been found in " << timeElapsed << " second(s)." << endl;

	return 0;
}


Enter a number greater than 1 : 10000000

Classic prime : 664579 prime number(s) have been found in 6.437 second(s).
Efficient prime : 664579 prime number(s) have been found in 0.329 second(s).


I absolutely don't understand the second algorithm, since I am an absolute beginner.
Also, I try removing this line :
isPrime(N);

It seems that this code is redundant, but when I remove it, the efficient method becomes much slower than the classic version! Can anyone please explain why?

Thanks :)
Last edited on
gunnerfunner (2127)
isPrime() is one version of the implementation of the Sieve of Eratosthenes method: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
Also, I try removing this line : isPrime(N); ... It seems that this code is redundant, ...

It is not redundant, it keeps the count variable ticking
And I am not sure about this method being faster always ... as Wikipedia mentions, it is more efficient for the smaller primes 
1
2
3
4
 
Enter a number greater than 1 : 200000

Classic prime : 17984 prime number(s) have been found in 0.027 second(s).
Efficient prime : 17984 prime number(s) have been found in 0.056 second(s).

integralfx (897)

Also, I try removing this line :
isPrime(N);

This allows the efficient method to pre-compute primes and as a result will always be faster than the traditional prime(constant time vs sqrt(a)).
Topic archived. No new replies allowed.