WANTED:
Please let me know if there is a better way ...!
I made a prime number generator with Python
In the previous article
--Use the all or any methods
--It is good to make it a function
I received a comment.
import time
def primes_up_to_(upper_limit): #Functionalization
if upper_limit < 2:
return []
primes_list = [2] #Save prime numbers in this list, only 2 is a prime number for even numbers
for integer in range(3, upper_limit + 1, 2): #For odd numbers of 3 or more
if all(integer % prime != 0 for prime in primes_list): #If it is not divisible by all prime
primes_list.append(integer) #Accept integer as a prime number and add it to primes
return primes_list
start_time = time.time() #Record start time
primes_list = primes_up_to_(10000) #Search for prime numbers by specifying a textual upper limit
elapsed_time = time.time() - start_time #elapsed time=Current time-Start time
print(primes_list)
print(len(primes_list), "prime numbers foud.")
print ("run time: {0}".format(elapsed_time) + " seconds")
It's more compact. I didn't know methods such as all, so I'm honored to comment.
Since I skipped two integers, the calculation time was shortened a little.
Last time, I was looking for a prime number by thinking that if a natural number is not divisible by a prime number smaller than that, I thought that the natural number is a prime number **, but the head family Eratosthenes Sieve
Stupid way 1: Judge whether it is a prime number in order from $ 1 $ to $ n $. 2: Whether $ k $ is a prime number or not can be divided by the prime numbers less than $ \ sqrt {k} $.
I didn't know the condition of 2.
2 causes $ \ sqrt {k} $ because $ k $ always has a prime factor smaller than $ \ sqrt {k} $ if it is a composite number.
Yeah ~ (stupid).
When I included this in the previous code, it became like this.
import time
import math
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
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 prime >= math.sqrt(integer): #If prime is greater than the square root of integer
break #There is no point in doing this for anymore.
elif integer % prime == 0: #If integer is divisible by prime, it's not a prime number,
is_divisible = True #Divisible
break #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")
In the previous one, it took about ** 4 minutes to search up to $ 10 ^ 6 $, but when I executed this, it took about 3.5 seconds **. I expected that the search up to $ 10 ^ 7 $ would take several hours with the previous one, but this time it took about 1 minute.
Ancient Greece is amazing.
Improvement 1 + Improvement 2.
import time
import math
def primes_up_to_(upper_limit): #Functionalization
if upper_limit < 2:
return []
primes_list = [2] #Save prime numbers in this list, only 2 is a prime number for even numbers
for integer in range(3, upper_limit + 1, 2): #For odd numbers of 3 or more
temp_primes_list = [] #add to
for prime in primes_list: #add to
if prime <= math.sqrt(integer): #add to
temp_primes_list.append(prime) #add to
if all(integer % prime != 0 for prime in temp_primes_list): #If it is not divisible by all prime
primes_list.append(integer) #Accept integer as a prime number and add it to primes
return primes_list
start_time = time.time() #Record start time
primes_list = primes_up_to_(10000) #Search for prime numbers by specifying a textual upper limit
elapsed_time = time.time() - start_time #elapsed time=Current time-Start time
print(primes_list)
print(len(primes_list), "prime numbers foud.")
print ("run time: {0}".format(elapsed_time) + " seconds")
Well, because the number of for loops has increased, the processing time has become longer.
Recommended Posts