I made a prime number generation program in Python 2

WANTED:

Please let me know if there is a better way ...!

Last time

I made a prime number generator with Python

Improvements from the last time

Improvement 1

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.

Improvement 2

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 3

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.

Continue

Recommended Posts

I made a prime number generation program in Python
I made a prime number generation program in Python 2
I made a payroll program in Python!
I made a Caesar cryptographic program in Python.
I made a prime number table output program in various languages
Prime number generation program by Python
Prime number 2 in Python
A program that determines whether a number entered in Python is a prime number
I made a python text
I made a program to check the size of a file in Python
I made a Line-bot using Python!
I made a fortune with Python.
I made a daemon with Python
When writing a program in Python
I made a simple typing game with tkinter in Python
I tried "a program that removes duplicate statements in Python"
I made a puzzle game (like) with Tkinter in Python
I made a program that solves the spot the difference in seconds
I made a character counter with Python
Project Euler # 7 "1000 1st prime number" in Python
I made a program to collect images in tweets that I liked on twitter with Python
I made a Hex map with Python
I searched for prime numbers in python
After studying Python3, I made a Slackbot
I created a password tool in Python.
I made a roguelike game with Python
I made a simple blackjack with Python
I made a configuration file with Python
I made a neuron simulator with Python
I made a web application in Python that converts Markdown to HTML
I made a Discord bot in Python that translates when it reacts
I tried to discriminate a 6-digit number with a number discrimination application made with python
[Python] I forcibly wrote a short Perlin noise generation function in Numpy.
I made a script in python to convert .md files to Scrapbox format
[IOS] I made a widget that displays Qiita trends in Pythonista3. [Python]
I made a python dictionary file for Neocomplete
I made a competitive programming glossary with Python
I made a weather forecast bot-like with Python.
A memo that I wrote a quicksort in Python
I made a GUI application with Python + PyQt5
I want to create a window in Python
Prime number enumeration and primality test in Python
I made a Twitter fujoshi blocker with Python ①
I wrote a class in Python3 and Java
A program that removes duplicate statements in Python
[Python] I made a Youtube Downloader with Tkinter.
[Memo] I tried a pivot table in Python
A simple Pub / Sub program note in Python
I tried adding a Python3 module in C
Judge whether it is a prime number [Python]
I made a random number graph with Numpy
I made a bin picking game with Python
I made a Mattermost bot with Python (+ Flask)
I made a Python Qiita API wrapper "qiipy"
Prime numbers in Python
[Beginner] What happens if I write a program that runs in php in Python?
I made a familiar function that can be used in statistics with Python
I made a module in C language to filter images loaded by Python
In Python, I made a LINE Bot that sends pollen information from location information.
Python program is slow! I want to speed up! In such a case ...
Check if the string is a number in python