A program that determines whether a number entered in Python is a prime number

Introduction

This is a "program that determines whether the input integer n is a prime number or a composite number" that I made after studying Python and learning the basic syntax. I also write it as my diary. I think there are still many points that have yet to be reached, but I would appreciate any advice.

Program principle

The method of determining the prime number this time was based on the fact that "for the input n, if the divisor of n is not a prime number up to √n, it is a prime number." See below for detailed proof. [Proof that n is a prime number if the natural number n is not divisible by all prime numbers less than or equal to √n](https://cartman0.hatenablog.com/entry/2017/10/23/%E8%87%AA % E7% 84% B6% E6% 95% B0n% E3% 81% 8C% E2% 88% 9An% E4% BB% A5% E4% B8% 8B% E3% 81% AE% E3% 81% 99% E3 % 81% B9% E3% 81% A6% E3% 81% AE% E7% B4% A0% E6% 95% B0% E3% 81% A7% E5% 89% B2% E3% 82% 8A% E5% 88 % 87% E3% 82% 8C% E3% 81% AA% E3% 81% 91% E3% 82% 8C)

Actual program

import math
from sympy import primerange
n = int(input("Enter the number you want to check if it is a prime number.>> "))
num = int(math.sqrt(n)) + 1
primlist = list(primerange(2,num)) #1

for i in primlist: #2
    if n % i == 0: #3
        print("Composite number.")
        break
    elif i == primlist[-1] :
        print("It is a prime number.")

Rough flow

  1. Create a prime number list with numbers up to √n.
  2. Divide n by the prime number list.
  3. When it is divisible, the message "Composite number." Is displayed. When you reach the end of the prime number list, "It is a prime number." Is displayed.

What you are actually doing

  1. is # 1 and created a prime number list by using SymPy's primerange.
  2. is # 2, which uses the for syntax to extract characters from the prime number list.
  3. is # 3, and it is judged by "whether or not the ** remainder ** of n divided by a prime number is 0" using the if syntax.

Reflections

I made a primality test for the first time, but I am personally satisfied with the work. However, as n becomes larger (more than 7 digits), the calculation speed becomes slower, so I would like to improve it somehow. Also, if you think about it, you didn't need to use math, so I'd like to fix it. This is my first self-made program, so I'm leaving it as a memorial this time. I feel that it is possible to perform prime factorization using this program, so I would like to modify it. Thank you for reading to the end.

Recommended Posts

A program that determines whether a number entered in Python is a prime number
Judge whether it is a prime number [Python]
I made a prime number generation program in Python
I made a prime number generation program in Python 2
A program that automatically determines whether an animation or a photo is entered when a person's image is input [python]
Prime number 2 in Python
A program that removes duplicate statements in Python
Check if the string is a number in python
[Python] A program that counts the number of valleys
[Python] A program that finds the shortest number of steps in a game that crosses clouds
A Python program in "A book that gently teaches difficult programming"
A general-purpose program that formats Linux command strings in python
I tried "a program that removes duplicate statements in Python"
Infinite prime number generator in Python3
Prime number generation program by Python
When writing a program in Python
Play a sound in Python assuming that the keyboard is a piano keyboard
[Python] Execution time when a function is entered in a dictionary value
I made a prime number table output program in various languages
A script that returns 0, 1 attached to the first Python prime number
What's new in datetime that is a bit more useful in Python 3
[Python] A program that creates stairs with #
I made a payroll program in Python!
Project Euler # 7 "1000 1st prime number" in Python
Write a Caesar cipher program in Python
Hash in Perl is a dictionary in Python
A program that plays rock-paper-scissors using Python
[Python] A program that rounds the score
[Python] A program that calculates the number of chocolate segments that meet the conditions
[Python] A program that calculates the number of socks to be paired
A memo that I wrote a quicksort in Python
Prime number enumeration and primality test in Python
Prime factorization of integers entered in Python ver.1
A simple Pub / Sub program note in Python
I made a Caesar cryptographic program in Python.
[Beginner] What happens if I write a program that runs in php in Python?
[Python] A program that calculates the number of updates of the highest and lowest records
Python program is slow! I want to speed up! In such a case ...
Write a super simple molecular dynamics program in python
Receive dictionary data from a Python program in AppleScript
Try embedding Python in a C ++ program with pybind11
Hello World is a simple web server that follows WSGI (Web Server Gateway Interface) in Python.
Find the part that is 575 from Wikipedia in Python
What's in that variable (when running a Python script)
In Python, create a decorator that dynamically accepts arguments Create a decorator
A shell program that becomes aho in multiples of 3
There is a pattern that the program did not stop when using Python threading
A note that runs an external program in Python and parses the resulting line
Prime numbers in Python
[Python] A program that compares the positions of kangaroos.
A Python program that converts ical data into text
MALSS, a tool that supports machine learning in Python
A program that automatically resizes the iOS app icon to the required image size in Python
[Python] Programming to find the number of a in a character string that repeats a specified number of times.
I made a program to collect images in tweets that I liked on twitter with Python
[Python] A program to find the number of apples and oranges that can be harvested
A Python program that collects tweets containing specific keywords daily and saves them in csv
How to test that Exception is raised in python unittest
A function that divides iterable into N pieces in Python
A program that removes specific characters from the entered text
Loop through a generator that returns a date iterator in Python