Today, I was learning to create a function in Python 3. The interested problem I took was generating prime numbers below a certain number. As this is a mathematical subject, I really enjoyed while writing the program.

The prime numbers is a set of numbers those have only 1 and its number as divisor, eg: 2, 3, 5, 7, 11, 13, 17, 19, 23 and so on. Twelve (12) is not prime number, because it has 1, 2, 3, 4, 6 and 12 as divisor.

After trying several times, I got optimal simple algorithm (It should be any other algorithm that more optimal than mine version). The source program were written in Python 3 as follows:

```
import time
def getprime(pmax):
primelist = list()
check = 1
while True:
check += 1
if check > pmax:
break
isprime = True
for p in primelist:
if p**2 > check:
break
if check % p == 0:
isprime = False
break
if isprime:
primelist.append(check)
return primelist
if __name__ == "__main__":
pmax = int(input("Maximum = "))
t1 = time.time()
primelist = getprime(pmax)
t2 = time.time()
for p in primelist:
print(p, end=", ")
print ("\n\r", t2-t1, "secs")
print (len(primelist), "numbers")
```

For prime numbers below 2,500,000, I got 183,072 numbers for about 19.9 seconds of producing prime numbers list using my notebook with i3 processor.

I was not satisfied for this achievement. I tried to write a script using PHP 7 with similar algorithm as follows:

```
<?php
function getprime($pmax){
$primelist = [];
$check = 1;
while (true) {
if (++$check > $pmax) break;
$isprime = true;
foreach ($primelist as $p){
if ($p**2 > $check) break;
if ($check % $p == 0){
$isprime = false;
break;
}
}
if ($isprime) $primelist[] = $check;
}
return $primelist;
}
$pmax = readline("Maximum = ");
$t1 = time();
$primelist = getprime($pmax);
$t2 = time();
foreach($primelist as $p){
echo $p .", ";
}
echo "\n".($t2-$t1)." secs";
echo "\n".count($primelist)." numbers";
```

Unbelievable, this script only need 3 seconds to generate similar prime numbers set.

So, if PHP-Cli is more faster than Python, why do I fall in love to Python programming language? The answer might be like in this article

## New Algorithm to Make Faster

There are many algorithm to generate prime numbers list. I found a new algorithm that make me shocks because of speed increasing drastically. That method is using sieve of Eratosthenes as described here

```
def sieve_for_primes_to(n):
size = n//2
sieve = [1]*size
limit = int(n**0.5)
for i in range(1,limit):
if sieve[i]:
val = 2*i+1
tmp = ((size-1) - i)//val
sieve[i+val::val] = [0]*tmp
return sieve
print [2] + [i*2+1 for i, v in enumerate(sieve_for_primes_to(10000000)) if v and i>0]
```

Wow, it takes only 0.2 seconds to generate prime numbers below 2,500,000.

## Comments

There are currently no comments on this article.

## Comment