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
