{"id":9035,"date":"2022-10-07T22:32:53","date_gmt":"2022-10-07T21:32:53","guid":{"rendered":"https:\/\/stevepedwards.today\/DebianAdmin\/?p=9035"},"modified":"2022-10-10T21:44:00","modified_gmt":"2022-10-10T20:44:00","slug":"equivalent-prime-numbers-programs-for-java-python-c-and-jscript-testing","status":"publish","type":"post","link":"https:\/\/stevepedwards.today\/DebianAdmin\/equivalent-prime-numbers-programs-for-java-python-c-and-jscript-testing\/","title":{"rendered":"Equivalent Prime Numbers Programs for Java, Python, C and JScript Testing"},"content":{"rendered":"
<\/div>\n

<\/path><\/svg><\/i> \"Loading\"<\/p>\n

<\/div>\n

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.<\/p>\n

I intend to test them speedwise on my much newer, super powerful Dell Inspiron 16 7610, that sports 16 processors and 16GB RAM.<\/p>\n

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:<\/p>\n

upper = 100\r\nfor i in range(2, upper + 1):\r\n    a = 0\r\n    for j in range(2, i):\r\n\r\n        if (i % j) == 0:\r\n            a = 1\r\n            #         break\r\n            # else:\r\n    if (a == 0):\r\n        print(i, end=' ')\r\nprint(\" Done\")<\/pre>\n
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:<\/p>\n
C: 8 seconds<\/p>\n
#include <stdio.h>\r\nint main()\r\n{\r\n    int i, j, a, input;\r\n    for (i = 2; i < 100000; i = i + 1)\r\n    {\r\n        a = 0;\r\n        for (j = 2; j < i; j = j + 1)\r\n            if (i % j == 0)\r\n                a = 1;\r\n        if (a == 0)\r\n            printf(\"%d \", (i));\r\n    }\r\n    printf(\" Done\\n\");\r\n    return 0;\r\n}<\/pre>\n
JavaScript: (node command line) 11\u00a0 seconds<\/p>\n
for (i = 2; i < 100000; i = i + 1) {\r\n  a = 0;\r\n  for (j = 2; j < i; j = j + 1) if (i % j == 0) a = 1;\r\n  if (a == 0) console.log(i);\r\n}\r\n<\/pre>\n
Python: 22 seconds<\/p>\n
upper = 100000\r\nfor i in range(2, upper + 1):\r\n    for j in range(2, i):\r\n        if (i % j) == 0:\r\n            break\r\n    else:\r\n        print(i, end=' ')\r\nprint(\" Done\")\r\n<\/pre>\n
Java: 8 seconds<\/p>\n
public class primes {\r\n    public static void main(String args[]) {\r\n        int i, j, a;\r\n        int limit = 100000;\r\n        for (i = 2; i <= limit; i = i + 1) {\r\n            a = 0;\r\n            for (j = 2; j < i; j = j + 1)\r\n                if (i % j == 0)\r\n                    a = 1;\r\n            if (a == 0)\r\n                System.out.print(\" \" + i);\r\n        }\r\n        System.out.print(\" Done\\n\");\r\n    }\r\n}<\/pre>\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.<\/p>\n
A more efficient algorithmn is Erastothenes Sieve, explained here:<\/p>\n
https:\/\/pi3.sites.sheffield.ac.uk\/tutorials\/week-3-prime-numbers<\/a><\/p>\n
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.<\/p>\n
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.<\/p>\n
C: 4 secs<\/p>\n
999983
\nThere were 78498 primes up to 1000000<\/p>\n
#include <stdio.h>\r\n#include <math.h>\r\n\r\n#define N 100000\r\n\r\nint main()\r\n{\r\n    int num[N], i, j;\r\n    int limit = sqrt(N);\r\n\r\n    for (i = 0; i < N; i++)\r\n        num[i] = i + 1;\r\n\r\n    for (i = 1; i <= limit; i++)\r\n    {\r\n        if (num[i] != 0)\r\n        {\r\n            for (j = pow(num[i], 2); j <= N; j = j + num[i])\r\n            {\r\n                num[j - 1] = 0;\r\n            }\r\n        }\r\n    }\r\n\r\n    printf(\"Sieve of Eratosthenes Method\\n\");\r\n    printf(\"To find Prime numbers from 2 to %d\\n\\n\", N);\r\n    for (i = 1; i < N; i++)\r\n    {\r\n        if (num[i] != 0)\r\n            printf(\"%d \", num[i]);\r\n    }\r\n\r\n    printf(\"\\n\");\r\n\r\n    return 0;\r\n}<\/pre>\n
Python:\u00a0 16 sec<\/p>\n
def apply_sieve(n):\r\n    a = [1]*(n+1)  \r\n    a[0] = 0  \r\n    a[1] = 0  \r\n    p = 2       \r\n    pmax = int(round(n**0.5)) + 1\r\n    while p < pmax:\r\n        while a[p] == 0:\r\n            p += 1\r\n        j = 2*p\r\n        while j < n:\r\n            a[j] = 0\r\n            j += p\r\n        p += 1\r\n    return [p for p in range(n+1) if a[p] == 1]\r\nN = 1000000 \r\nprimes = apply_sieve(N)\r\nprint(primes)\r\n<\/pre>\n
JS:\u00a0 21 secs<\/p>\n
const num = 100000;\r\nconst findPrimes = (num = 10) => {\r\n  const numArr = new Array(num + 1);\r\n  numArr.fill(true);\r\n  numArr[0] = numArr[1] = false;\r\n  for (let i = 2; i <= Math.sqrt(num); i++) {\r\n    for (let j = 2; i * j <= num; j++) {\r\n      numArr[i * j] = false;\r\n    }\r\n  }\r\n  return numArr.reduce((acc, val, ind) => {\r\n    if (val) {\r\n      return acc.concat(ind);\r\n    } else {\r\n      return acc;\r\n    }\r\n  }, []);\r\n};\r\nconsole.log(findPrimes(num));\r\n<\/pre>\n
541,<\/span>
\n... 78398 more items<\/span><\/p>\n
Java: 6 secs<\/p>\n
\/**\r\n * Implementation of the sieve of Eratosthenes for finding all the primes up to\r\n * a given number (MAX in this case).\r\n * From the command line:\r\n *   Step 1 (compile): javac PrimesSieve.java\r\n *   Step 2 (run):     java PrimesSieve\r\n *\/\r\npublic class PrimeSieve {\r\n    public static void main(String[] args) {\r\n      final int MAX = 1_000_000;\r\n      \/\/ Create an array of boolean values indicating whether a number is prime.\r\n      \/\/ Start by assuming all numbers are prime by setting them to true. \r\n      boolean[] primes = new boolean[MAX];\r\n      for (int i=0; i<primes.length; i++) {\r\n        primes[i] = true;\r\n      }\r\n  \r\n      \/\/ Loop through a portion of the array (up to the square root of MAX). If\r\n      \/\/ it's a prime, ensure all multiples of it are set to false, as they\r\n      \/\/ clearly cannot be prime.\r\n      for (int i=2; i<Math.sqrt(MAX)+1; i++) {\r\n        if (primes[i-1]) {\r\n          for (int j=(int) Math.pow(i,2); j<=MAX; j+=i) {\r\n            primes[j - 1] = false;\r\n          }\r\n        }\r\n      }\r\n  \r\n      \/\/ Output the results\r\n      int count = 0;\r\n      for (int i = 2; i < MAX; i++) {\r\n        if (primes[i - 1]) {\r\n          System.out.println(i);\r\n          count++;\r\n        }\r\n      }\r\n      System.out.printf(\"There were %d primes up to %d\", count, MAX);\r\n    }\r\n  }<\/pre>\n
999983<\/span>
\nThere were 78498 primes up to 1000000<\/span><\/p>\n
 <\/p>\n","protected":false},"excerpt":{"rendered":"
<\/div>\n
<\/path><\/svg><\/i> \"Loading\"<\/p>\n
<\/div>\n
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 ...\u00a0 Equivalent Prime Numbers Programs for Java, Python, C and JScript Testing<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[],"class_list":["post-9035","post","type-post","status-publish","format-standard","hentry","category-post"],"a3_pvc":{"activated":true,"total_views":2,"today_views":0},"_links":{"self":[{"href":"https:\/\/stevepedwards.today\/DebianAdmin\/wp-json\/wp\/v2\/posts\/9035","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/stevepedwards.today\/DebianAdmin\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/stevepedwards.today\/DebianAdmin\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/stevepedwards.today\/DebianAdmin\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/stevepedwards.today\/DebianAdmin\/wp-json\/wp\/v2\/comments?post=9035"}],"version-history":[{"count":34,"href":"https:\/\/stevepedwards.today\/DebianAdmin\/wp-json\/wp\/v2\/posts\/9035\/revisions"}],"predecessor-version":[{"id":9082,"href":"https:\/\/stevepedwards.today\/DebianAdmin\/wp-json\/wp\/v2\/posts\/9035\/revisions\/9082"}],"wp:attachment":[{"href":"https:\/\/stevepedwards.today\/DebianAdmin\/wp-json\/wp\/v2\/media?parent=9035"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/stevepedwards.today\/DebianAdmin\/wp-json\/wp\/v2\/categories?post=9035"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/stevepedwards.today\/DebianAdmin\/wp-json\/wp\/v2\/tags?post=9035"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}