I did a post a long way back on Primes and Erastothenes Sieve not knowing how "equivalent" the code is between languages, but now I have 4 version that seem identical as can be.
I intend to test them speedwise on my much newer, super powerful Dell Inspiron 16 7610, that sports 16 processors and 16GB RAM.
A very basic test for each in VScode was surprising. The main issue being disimilar functioning of the way python runs without an if/break/else line, as it really doesn't like the iteration process the others handle ok - it takes about 7+ minutes to run this way once at 100k primes or above:
upper = 100
for i in range(2, upper + 1):
a = 0
for j in range(2, i):
if (i % j) == 0:
a = 1
# break
# else:
if (a == 0):
print(i, end=' ')
print(" Done")
From hitting the run button for each against a clock 2nd hand, so including any VSCode compilation that needs doing, gave the following results to print primes up to 100,000:
C: 8 seconds
#include <stdio.h>
int main()
{
int i, j, a, input;
for (i = 2; i < 100000; i = i + 1)
{
a = 0;
for (j = 2; j < i; j = j + 1)
if (i % j == 0)
a = 1;
if (a == 0)
printf("%d ", (i));
}
printf(" Done\n");
return 0;
}
JavaScript: (node command line) 11 seconds
for (i = 2; i < 100000; i = i + 1) {
a = 0;
for (j = 2; j < i; j = j + 1) if (i % j == 0) a = 1;
if (a == 0) console.log(i);
}
Python: 22 seconds
upper = 100000
for i in range(2, upper + 1):
for j in range(2, i):
if (i % j) == 0:
break
else:
print(i, end=' ')
print(" Done")
Java: 8 seconds
public class primes {
public static void main(String args[]) {
int i, j, a;
int limit = 100000;
for (i = 2; i <= limit; i = i + 1) {
a = 0;
for (j = 2; j < i; j = j + 1)
if (i % j == 0)
a = 1;
if (a == 0)
System.out.print(" " + i);
}
System.out.print(" Done\n");
}
}
These programs are very inefficient because they re-run the division by 2 Prime check as each new prime is found, so waste more and more cycles as the amount of primes found increases.
A more efficient algorithmn is Erastothenes Sieve, explained here:
https://pi3.sites.sheffield.ac.uk/tutorials/week-3-prime-numbers
Python redeems itself with primes up to 1M printed in 13 seconds.using the Sieve method, not having to start the divisor loop from 2 each time, only continuing on from where the last prime was found - massive saving of wasted re-iterations.
Now, I just have to transpose a Sieve version for the other langs...if my rudimentary programming abilities allow...in the meantime here's some non equivalent Sieve times up to 1M primes for Java and JS and Python.
C: 4 secs
999983
There were 78498 primes up to 1000000
#include <stdio.h>
#include <math.h>
#define N 100000
int main()
{
int num[N], i, j;
int limit = sqrt(N);
for (i = 0; i < N; i++)
num[i] = i + 1;
for (i = 1; i <= limit; i++)
{
if (num[i] != 0)
{
for (j = pow(num[i], 2); j <= N; j = j + num[i])
{
num[j - 1] = 0;
}
}
}
printf("Sieve of Eratosthenes Method\n");
printf("To find Prime numbers from 2 to %d\n\n", N);
for (i = 1; i < N; i++)
{
if (num[i] != 0)
printf("%d ", num[i]);
}
printf("\n");
return 0;
}
Python: 16 sec
def apply_sieve(n):
a = [1]*(n+1)
a[0] = 0
a[1] = 0
p = 2
pmax = int(round(n**0.5)) + 1
while p < pmax:
while a[p] == 0:
p += 1
j = 2*p
while j < n:
a[j] = 0
j += p
p += 1
return [p for p in range(n+1) if a[p] == 1]
N = 1000000
primes = apply_sieve(N)
print(primes)
JS: 21 secs
const num = 100000;
const findPrimes = (num = 10) => {
const numArr = new Array(num + 1);
numArr.fill(true);
numArr[0] = numArr[1] = false;
for (let i = 2; i <= Math.sqrt(num); i++) {
for (let j = 2; i * j <= num; j++) {
numArr[i * j] = false;
}
}
return numArr.reduce((acc, val, ind) => {
if (val) {
return acc.concat(ind);
} else {
return acc;
}
}, []);
};
console.log(findPrimes(num));
541,
... 78398 more items
Java: 6 secs
/**
* Implementation of the sieve of Eratosthenes for finding all the primes up to
* a given number (MAX in this case).
* From the command line:
* Step 1 (compile): javac PrimesSieve.java
* Step 2 (run): java PrimesSieve
*/
public class PrimeSieve {
public static void main(String[] args) {
final int MAX = 1_000_000;
// Create an array of boolean values indicating whether a number is prime.
// Start by assuming all numbers are prime by setting them to true.
boolean[] primes = new boolean[MAX];
for (int i=0; i<primes.length; i++) {
primes[i] = true;
}
// Loop through a portion of the array (up to the square root of MAX). If
// it's a prime, ensure all multiples of it are set to false, as they
// clearly cannot be prime.
for (int i=2; i<Math.sqrt(MAX)+1; i++) {
if (primes[i-1]) {
for (int j=(int) Math.pow(i,2); j<=MAX; j+=i) {
primes[j - 1] = false;
}
}
}
// Output the results
int count = 0;
for (int i = 2; i < MAX; i++) {
if (primes[i - 1]) {
System.out.println(i);
count++;
}
}
System.out.printf("There were %d primes up to %d", count, MAX);
}
}
999983
There were 78498 primes up to 1000000