Primality test with python

Introduction

This is an article for beginners by beginners.

I was solving the problem this time as well, and finally I was able to solve it, so I am writing this article with the intention of sharing it as a memorandum.

This time, we will create a program to determine whether a natural number is a prime number!

Program creation

Well, I will create it at once.

First of all, I would like to briefly mention what a prime number is.

-Prime number: 1 and a number that can only be divided by the number itself (1 is not included)

In other words, I thought it would be good to divide that number by the number from 2 to (the number-1) and check the remainder!

Therefore, we will define a function called p_judge. (The reason for p is that prime numbers are often represented by p in mathematical problems.)

#Define function
def p_judge(a):

Now, let's think about how to process it. First of all, there is a task of substituting a number from 2 to (the number-1) and dividing it, so it seems that ** for statement ** can be used!

Also, the process is likely to branch to determine if it is a prime number or not. Therefore, it seems that ** if statement ** can be used!

From the above, I thought that combining for and if would work.

The following is the program that shows the process

#Define function
def p_judge(a):
    for x in range(2,a):#From 2 (number to check-Substitute to x up to 1)
        if a%x == 0:#If a ÷ x is divisible
            print('False')#Output False
            return#Return to the caller of the function.
    print('True')#After clearing all the above programs, output True

This looks good! !! I wrote the comments in detail for easy understanding. If you make a mistake, please point it out.

This completes the outline! All you have to do is place the input to receive the value, and add a little more description to use the well-defined function.

The following is the completed program

a = input()#Receive a value (at this time, receive it as a string)
a = int(a)#Convert a received as a string to an integer

def p_judge(a):
    for x in range(2,a):#From 2 (number to check-Substitute to x up to 1)
        if a%x == 0:#If a ÷ x is divisible
            print('False')#Output False
            return#Return to the caller of the function.

    print('True')#After clearing all the above programs, output True

p_judge(a)#Then, for a, the function p_Use judge

Yes, it's done! !!

Digression

It took me a long time to make this program ... Because I didn't know return, if and for.

I thought if and for were functions, so I usually wrote them with return inside. So, I was always going crazy with an error saying'return outside function'lol

You solved this by defining a new function. I'm still a beginner, so there are many things I don't understand, but I think it's too difficult at this level. Tohoho ...

Postscript

We have received some comments, so we will modify the program!

(1) It is better to use a function that returns True and False instead of print.

→ It seems that you should erase the print part and change it to return.

(2) It is better to consider the processing when 1, 0 or a negative number is given as an argument.

→ It seems that it will work if you play with the if statement a little.

For the time being, if you reflect these ① and ②, it will look like this.

a = input()
a = int(a)

def p_judge(a):
    if a <= 1:#If a is less than or equal to 1
        return False#Returns False
    for x in range(3,a,2):#3 to a-Substitute x for numbers that increase by 2 up to 1
        if a%x == 0:
            return False#Returns False
        
    return True#Returns True

print(p_judge(a))

This is the part where the comment is written.

I tried to put it in one if statement using or, but it didn't work and I had to split it into two ...

It is these two points that will be corrected next.

(3) Even numbers are not prime numbers other than 2, so processing only 2 and even numbers can be done first, and processing time can be reduced by looping only odd numbers.

④ You can check up to the square root to see if it is divisible.

First, we will correct ③. This seems to be good if you attach if again. In other words, even numbers other than 2 should be excluded. The following program reflects this.

a = input()
a = int(a)

def p_judge(a):
    if a == 2:#If a is 2
        return True#Returns True
    elif a <= 1 or a%2 == 0:#If a is less than or equal to 1 or a is divisible by 2
        return False#Returns False
    for x in range(3,a,2):
        if a%x == 0:
            return False
        
    return True

print(p_judge(a))

By the way, regarding ④, I myself learned this fact for the first time ... lol If you ask me, that's certainly the case. In the case of composite numbers, there are divisors, but there are pairs of divisors. (For example, 64 is 4x16 and 16x4, etc.) And that number of turning points is just the square root. (If it is 64, it will be folded back at 8x8), so if you look up to the square root, you don't have to look beyond that. We will reflect this in the program.

The square root is represented by a method called sqrt in the math module. Then, in order to truncate the value after the decimal point, we also use a method called floor in the math module.

The following is the modified program.

import math#import math module

a = input()
a = int(a)

a = math.sqrt(a)#Use sqrt to represent the square root of a
a = math.floor(a)#Use floor to truncate a after the decimal point

def p_judge(a):
    if a == 2:
        return True
    elif a <= 1 or a%2 == 0:
        return False
    for x in range(3,a+1,2):#Because a has changed+1 need to
        if a%x == 0:
            return False
        
    return True

print(p_judge(a))

That's all! !! Thank you to everyone who commented!

in conclusion

This time, I made a primality test program. If you have any advice, please feel free to comment and I will reflect it in the article each time.

Thank you for reading until the end! !! !!

Recommended Posts

Primality test with python
Primality test by Python
Algorithm in Python (primality test)
Unit test log output with python
FizzBuzz with Python3
Scraping with Python
Scraping with Python
Python with Go
Twilio with Python
Integrate with Python
Play with 2016-Python
AES256 with python
Tested with Python
python starts with ()
with syntax (Python)
Python Integrity Test
Bingo with python
Zundokokiyoshi with python
Excel with Python
Microcomputer with Python
Cast with python
[Python] Super easy test with assert statement
Stress Test with Locust written in Python
Test Python non-functional programs with GitLab CI
WebUI test with Python2.6 + Selenium 2.44.0 --profile setting
Generate Japanese test data with Python faker
Post Test 3 (Working with PosgreSQL in Python)
How to do portmanteau test with python
Integrating with setuptools / python setup.py test / pytest-runner
Serial communication with Python
Zip, unzip with python
Django 1.11 started with Python3.6
Python with eclipse + PyDev.
Socket communication with Python
Data analysis with python 2
Scraping with Python (preparation)
Try scraping with Python.
Strengthen with code test ⑦
Learning Python with ChemTHEATER 03
Sequential search with Python
"Object-oriented" learning with python
Create test data like that with Python (Part 1)
Handling yaml with python
Solve AtCoder 167 with python
Serial communication with python
[Python] Use JSON with Python
Strengthen with code test ⑨
Learning Python with ChemTHEATER 05-1
Strengthen with code test ③
Learn Python with ChemTHEATER
Run prepDE.py with python3
1.1 Getting Started with Python
Collecting tweets with Python
Binarization with OpenCV / Python
3. 3. AI programming with Python
Kernel Method with Python
Scraping with Python + PhantomJS
Python basics 8 numpy test
Prime number enumeration and primality test in Python
Python test package memo
Drive WebDriver with python