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!
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! !!
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 ...
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!
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