C vs Python

Postanowiłem porównać szybkość znajdowania liczb pierwszych w językach programowania C i Python najprostszym algorytmem sprawdzającym dzielniki badanej liczby.

Dla przypomnienia: Liczba pierwsza to liczba naturalna, która ma dokładnie dwa dzielniki naturalne - jedynkę i samą siebie. Wykaz początkowych liczb pierwszych: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271 itd. Liczby naturalne większe od 1, które nie są pierwsze, nazywa się liczbami złożonymi. Liczby 4 i 6 są więc przykładami liczb złożonych. Z podanych definicji wynika, że liczby 0 i 1 nie są ani pierwsze, ani złożone. Liczby pierwsze są stosowane w niektórych algorytmach kryptograficznych np. RSA.

Algorytm jest bardzo prosty: dla badanej liczby naturalnej n sprawdzamy, czy liczby naturalne należące do przedziału [2, ... ,  √n] są dzielnikami naszej liczby n. Jeżeli okazało by się, że któraś z tych liczb jest dzielnikiem naszej liczby n, oznacza to, że nasza liczba nie jest pierwsza.

Mój test polega na tym, że mierzony jest czas sprawdzenia 8 milionów liczb, czy są liczbami pierwszymi. Pierwszy program jest napisany w języku C:

#include <stdio.h>
#include <math.h>
#include <time.h>

#define FALSE 0
#define TRUE  1
  
int is_prime(int n) {
  if (n<2) {
    return FALSE;
  }
  else if (n==2) {
    return TRUE;
  }
  else {
    for (int i=2; i<=(int)ceil(sqrt(n)); i++) {
      if (n % i == 0) {
        return FALSE;
      }
    }
    return TRUE;
  }
}

int main() {
  int max = 8000000;
  time_t t1, t2;
  
  printf("Checking %d numbers. Please wait...\n", max);
  
  t1 = time(NULL);
  
  for(int i=1; i<=max; i++) {
    is_prime(i);
    //printf("%d   %d\n", i, is_prime(i));
  }
  
  t2 = time(NULL);
  printf("Done in %ld seconds.\n", t2-t1);
}

Program kompilujemy następująco:

gcc primes-search.c -o primes-search -lm

lub

cc primes-search.c -o primes-search -lm

Drugi program jest w języku Python 3:

import math
import time

def is_prime(n):
  if n < 2:
    return False
  elif n == 2:
    return True
  else:
    # range = 2..math.ceil(math.sqrt(n))
    for i in range(2, (int)(math.ceil(math.sqrt(n))) + 1):
      if n % i == 0:
        return False
    return True
    

max = 8000000

print("Checking %d numbers. Please wait..." % max)

t1 = time.time()

for i in range(1, max):
  is_prime(i)
  #print("%d   %d" % (i, is_prime(i)))
  
t2 = time.time()
print("Done in %d seconds." % (t2-t1))

Kody źródłowe są tutaj:

https://github.com/adamblaszczyk/primes-search__c_vs_python

Czasy wykonania programów:

LENOVO ThinkPad E440, Intel Core i3-4000M 2.4GHz - FreeBSD 13.0 64-bit

.c - 21 sekund

.py - 124 sekundy