We know that one of the most critical metrics is how quickly it can execute code.
It is impossible to expect the deadline when the competition between C++, JavaScript, and PHP will be over.
Most of the developers want to know which is the fastest between them. So do I.
I’ve checked out their code-running speed through the problem which counts the primes from 1 to n.
By Euclid’s theorem, there are an infinite number of prime numbers.
In case that n is 10000000, the total number of primes becomes 664579, such as 2, 3, 5, 7, 9, …, 9999971, 9999973, 9999991.
I’ve used 3 methods for its solution.
Method 1: Given a number a, check if there are any divisors from 2 to sqrt(a), then the number is not a prime. This is the common method, there is no need to use any array or object for the implementation.
Method 2: This is to use the Sieve of Eratosthenes, which is an efficient way to count the number of prime numbers up to a given limit. The key optimization in this method is that instead of checking each number from 2 to n for primality, it only checks the numbers that are not divisible by the prime numbers already found. This significantly reduces the number of computations required, making the algorithm more efficient, especially for large values of n. The time complexity of this implementation of the Sieve of Eratosthenes algorithm is O(n * log(log(n))), which is quite efficient compared to the naive approach of checking each number for primality, which would have a time complexity of O(n * sqrt(n)).
Method 3: This is also to use the Sieve of Eratosthenes, but with a slightly different implementation. The key difference between this implementation and the previous one is that instead of using an array to store the prime numbers, it uses a boolean array bo to keep track of which numbers are prime and which are not. This approach can be more memory-efficient for large values of n, as it only requires a single bit of memory per number, rather than an entire integer. The time complexity of this implementation of the Sieve of Eratosthenes algorithm is also O(n * log(log(n))), which is the same as the previous implementation.
C++ code:
#include <bits/stdc++.h>
using namespace std;
int countPrimes1(int n) {
int i, j, cnt = 0;
for (i = 2; i <= n; i++) {
for (j = 2; j * j <= i && i % j; j++);
cnt += (j * j > i);
}
return cnt;
}
int countPrimes2(int n) {
int i, j, cnt = 0, *pr = new int[n];
for (i = 2; i <= n; i++) {
for (j = 0; j < cnt && pr[j] * pr[j] <= i && i % pr[j]; j++);
if (!(j < cnt && pr[j] * pr[j] <= i)) pr[cnt++] = i;
}
return cnt;
}
int countPrimes3(int n) {
int i, j, cnt = 0;
bool *bo = new bool[n + 1];
for (memset(bo, 0, n + 1), i = 2; i * i <= n; i++)
if (!bo[i]) for (cnt++, j = i * i; j <= n; j += i) bo[j] = 1;
for (; i <= n; i++) cnt += !bo[i];
return cnt;
}
int main() {
int n = 10000000;
double tt = clock();
printf("%dn", countPrimes1(n));
printf("%.0lf ms elapsed...nn", clock() - tt);
tt = clock();
printf("%dn", countPrimes2(n));
printf("%.0lf ms elapsed...nn", clock() - tt);
tt = clock();
printf("%dn", countPrimes3(n));
printf("%.0lf ms elapsed...nn", clock() - tt);
}
Execution result:
enter image description here
JavaScript code:
const countPrimes1 = n => {
let i, j, cnt = 0;
for (i = 2; i <= n; i++) {
for (j = 2; j * j <= i && i % j; j++);
cnt += (j * j > i);
}
return cnt;
}
const countPrimes2 = n => {
let i, j, cnt = 0, pr = [];
for (i = 2; i <= n; i++) {
for (j = 0; j < cnt && pr[j] * pr[j] <= i && i % pr[j]; j++);
if (!(j < cnt && pr[j] * pr[j] <= i)) pr[cnt++] = i;
}
return cnt;
};
const countPrimes3 = n => {
let i, j, cnt = 0, bo = [];
for (i = 2; i * i <= n; i++)
if (!bo[i]) for (cnt++, j = i * i; j <= n; j += i) bo[j] = 1;
for (; i <= n; cnt += !bo[i++]);
return cnt;
};
let tt = Date.now(), n = 10000000;
console.log(countPrimes1(n));
console.log(Date.now() - tt, "ms elapsed...n"); tt = Date.now();
console.log(countPrimes2(n));
console.log(Date.now() - tt, "ms elapsed...n"); tt = Date.now();
console.log(countPrimes3(n));
console.log(Date.now() - tt, "ms elapsed...n"); tt = Date.now();
Execution result:
enter image description here
PHP code:
<?php
ini_set("memory_limit", "-1");
function countPrimes1($n) {
for ($cnt = 0, $i = 2; $i <= $n; $i++) {
for ($j = 2; $j * $j <= $i && $i % $j; $j++);
$cnt += ($j * $j > $i);
}
return $cnt;
}
function countPrimes2($n) {
$pr = [];
for ($cnt = 0, $i = 2; $i <= $n; $i++) {
for ($j = 0; $j < $cnt && $pr[$j] * $pr[$j] <= $i && $i % $pr[$j]; $j++);
if (!($j < $cnt && $pr[$j] * $pr[$j] <= $i)) $pr[$cnt++] = $i;
}
return $cnt;
}
function countPrimes3($n) {
$bo = [];
for ($cnt = 0, $i = 2; $i * $i <= $n; $i++)
if (empty($bo[$i])) for ($cnt++, $j = $i * $i; $j <= $n; $j += $i) $bo[$j] = 1;
for (; $i <= $n; $i++) if (empty($bo[$i])) $cnt++;
return $cnt;
}
$n = 10000000;
$tt = microtime(true);
printf("%dn", countPrimes1($n));
printf("%.0lf ms elapsed...nn", (microtime(true) - $tt) * 1000);
$tt = microtime(true);
printf("%dn", countPrimes2($n));
printf("%.0lf ms elapsed...nn", (microtime(true) - $tt) * 1000);
$tt = microtime(true);
printf("%dn", countPrimes3($n));
printf("%.0lf ms elapsed...nn", (microtime(true) - $tt) * 1000);
Execution time:
enter image description here
Oh my gosh, I am surprised that PHP is much slower.
What do those screens imply to us?
I am confused to decide which is the fastest.
I’ve tried to decide which is the fastest of C++, JavaScript, and PHP, the most popular programming languages.
Oleh is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.