I made a prime number generation program in Python

Idea

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.

code

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

About execution time

-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

Continue

I made a prime number generator with Python 2

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!
Infinite prime number generator in Python3
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 made a quick feed reader using feedparser 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
Write a Caesar cipher program in 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
I tried playing a typing game 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"
〇✕ I made a game
Prime numbers in Python
[Beginner] What happens if I write a program that runs in php in Python?