If a natural number is not divisible by a smaller prime number, then that natural number is a prime number.
I wrote a program with the idea.
I prepared a list and saved the prime numbers in that list one after another.
import time
primes_list = [] #Save prime numbers in this list
upper_lim = 10000 #Set a textual number
start_time = time.time() #Record start time
for integer in range(2, upper_lim + 1, 1): # 2-For an integer of 10000
if len(primes_list) < 1 : # primes_If list is empty
primes_list.append(integer) # primes_integer in list(=2)To add
else: #In other cases (main subject),
is_divisible = False #Assume that integer is indivisible, that is, prime
for prime in primes_list: #All prime numbers saved so far"prime"about,
if integer % prime == 0: #If integer is divisible by prime
is_divisible = True #Divisible (that is, not a prime number)
break #Then there is no point in doing this for anymore.
#If integer is a composite number, is some prime_divisible =Become True
if not is_divisible: #After making this decision for all primes, it's still is_divisible =If False, it's already a prime number
primes_list.append(integer) #Recognize integer as a prime number and prime_Add to list
print(primes_list)
print(len(primes_list), "prime numbers foud.")
elapsed_time = time.time() - start_time #elapsed time=Current time-Start time
print ("run time: {0}".format(elapsed_time) + " seconds")
output:
$ python prime_numbers.py
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37,
（...abridgement...）
9883, 9887, 9901, 9907, 9923, 9929, 9931, 9941, 9949, 9967, 9973]
1229 prime numbers foud.
run time: 0.0615689754486084 seconds
-Search up to $ 10 ^ 2 $: about 0.0001 s -Search up to $ 10 ^ 3 $: about 0.001 s -Search up to $ 10 ^ 4 $: about 0.06 s -Search up to $ 10 ^ 5 $: about 4 s -Search up to $ 10 ^ 6 $: 240 s = about 4 min -After $ 10 ^ 7 $: ??? A few hours?
The environment is
I made a prime number generator with Python 2
Recommended Posts