Welcome!
This is the community forum for my apps Pythonista and Editorial.
For individual support questions, you can also send an email. If you have a very short question or just want to say hello — I'm @olemoritz on Twitter.
Prime number finder
-
I have some python prime number code which finds out prime numbers. I was looking for a way to make it more efficient as this currently checks for all factors until it reachers the number, it possible could you make the explainations simple as I am 13. Here is the code:
import time print('Made by Yasas Kulatunga, Dhari Prashanth and Dhivy Prashanth') print(' ') number = int(input("Enter a Number: ")) print(' ') time.sleep(0.5) print('THINKING.') time.sleep(0.5) print('THINKING..') time.sleep(0.5) print('THINKING...') time.sleep(0.5) print(' ') c = 0 while number: for i in range(2,number): if number % i == 0: print(str(i),"times",str(number//i),"is",str(number)) time.sleep(0.3) c = c + 1 if c == 0: print(' ') print(str(number),"has no factors apart from 1 and itself, therefore it is a prime number") print(' ') time.sleep(0.3) else: print(' ') print(str(number),"is not a prime number, the number has factors more than 1 and the number itself.") print(' ') time.sleep(0.3) number = int(input('Enter a number: ')) print(' ') time.sleep(0.3) c = 0
-
I never used a for / else loop before but here it works well. When we find the first factor, we print a not prime message and then fast fail out of the loop with break. If the loop finishes without a break then we use the else clause to tell the use that we have a prime number.
Let's call this the 5F approach: finding first factor fast fail...
import time print('Made by Yasas Kulatunga, Dhari Prashanth and Dhivy Prashanth') print(' ') number = int(input("Enter a Number: ").strip()) print(' ') time.sleep(0.5) print('THINKING.') time.sleep(0.5) print('THINKING..') time.sleep(0.5) print('THINKING...') time.sleep(0.5) print(' ') while number: for i in range(2, number): if number % i == 0: print('{} is not prime.'.format(number)) break else: print('{} is prime!'.format(number)) number = int(input("Enter a Number: ").strip())
-
More efficient way would be to check the number for divisibility, only till its' square root - 1.
Because the largest factor of any number cannot exceed it's square root, there is no need for range to go beyond that.
With minimal alteration to script given by @ccc , this would be more efficient.# Revised as per bug reported by @cvp # This code takes care of numbers 1 and 2 also. import time from math import sqrt print('Made by Yasas Kulatunga, Dhari Prashanth and Dhivy Prashanth') print(' ') number = int(input("Enter a Number: ").strip()) maxfact = int(sqrt(number)+1) print(' ') time.sleep(0.5) print('THINKING.') time.sleep(0.5) print('THINKING..') time.sleep(0.5) print('THINKING...') time.sleep(0.5) print(' ') while number: for i in range(2, maxfact): if number % i == 0: print('{} is not prime.'.format(number)) break else: print('{} is prime!'.format(number)) number = int(input("Enter a Number: ").strip()) maxfact = int(sqrt(number)+1)
-
The above implementations do not deal with the fact that all values less than 2 are not prime.
https://primes.utm.edu/notes/faq/one.html
https://www.reference.com/math/0-prime-number-1964bd6272594f3f
https://primes.utm.edu/notes/faq/negative_primes.html -
Bug, try with 25
maxfact = int(sqrt(number)-1) -> maxfact = int(sqrt(number))
-
Bug, try with 25
for i in range(2, maxfact+1):
-
Check if 2 is a divisor but skip all other even divisors
(Perhaps what @ccc minded with "less than 2")for i in [2]+list(range(3, maxfact+1,2)):
-
The exact output is this, although it is from the original code I posted on top: Enter a Number: 25
THINKING.
THINKING..
THINKING...5 times 5 is 25
25 is not a prime number, the number has factors more than 1 and the number itself.
Enter a number:
-
Sorry, I had tested the last code of @ramvee until √ - 1
-
But he was almost right, you have to check only until sqrt(number),
And, what I just added, by skipping the even divisors!For instance, if number is 29, your code checks the division by
2 3 4 5 6 7 8 9 10 11 12 13 ...29
But "mine" (& @ramvee) only
2 3 5 -
@cvp, If you go the the three vertical dots at the upper right of your forum post, you can edit it to add new insights. This is probably a better approach than replying to your own posts.
-
@ccc, Thanks, I knew it but sometimes I forget it, and sometimes I'm not sure how other people see an update, while I'm sure they see a new response
-
@cvp
Thank you for pointing the bug in my code. :)I put in your line of code
for i in [2]+list(range(3, maxfact+1,2)):
and it works fine,
Except it shows 2 is not a prime.. If we sort this we're good.. I think.. -
I think the consecutive 3 post's from @cvp might have been better done in edit. Maybe and maybe not. If the items inside a post themselves were also threaded , then it would be clear to do like that. But they are not. Just saying it's not a clear cut choice.
-
-
@cvp , lol, yes he is normally right. But need to keep him on his toes. 😱😈