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