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.
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)
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.")
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