+ 5

Prime Number

Someone from our beautiful community can be kind enough to explain how to create and understand an algorithm that searches for prime numbers? I ask because I wanted to write to participate in some CHALLENGE as emirp,goldbach conjecture ecc I've seen some algorithms of those that run here but I did not understand them 😱😱😞 can you help me?

5th Oct 2018, 11:09 AM
<StraMa/Design>
<StraMa/Design> - avatar
10 Answers
+ 5
Do you want to test whether a number is prime? Here's the idea: You probably know that a prime number is a positive integer that has EXACTLY TWO divisors: 1 and itself. So the first few primes are 2, 3, 5, 7, 11, etc. Now say we want to create a function that tests if an integer n is prime. First we check if n is 1 or smaller. Because if it is, then it's automatically not a prime, and we return False. Next, we want to check if it has a divisor bigger than 1 but smaller than itself. To do that, we'll need to iterate over the integers between 2 and n-1. But how to check if n is divisible by an integer? Hint: Divisible means zero remainder, so use the % operator. So when n is divisible by one of those numbers, we can immediately conclude that that it is not prime, and we return False. Lastly, if n is not divisible by any of those numbers, it must be a prime, so we return True. Does that make sense? Let me know if something sounds confusing.
5th Oct 2018, 11:25 AM
Kishalaya Saha
Kishalaya Saha - avatar
+ 5
Well the most popular prime number generation algorithm is the sieve of Erathnostenes, a greek Mathematician. The algorithm is as follows: 1. Start with "2" Cancel all multiple of 2. The smallest number left (ignore 1) is 3. Repeat this algorithm again and again with the smallest numbers not cancelled. These numbers are prime numbers.
5th Oct 2018, 11:26 AM
👑 Prometheus 🇸🇬
👑 Prometheus 🇸🇬 - avatar
+ 5
Here's a pseudocode summing up what I said: function is_prime(n) if n ≤ 1 return false for i = 2, 3, ... n-1 if n is divisible by i return false return true Can you turn this into a working Python code? If you get stuck, just post the code, and we'll help you out! This is very basic. It can be vastly improved. But let's start with something simple 😊
5th Oct 2018, 11:31 AM
Kishalaya Saha
Kishalaya Saha - avatar
+ 5
Kishalaya Saha Thank you so much for your explanation !! I understood the base very well and thanks to your pseudocode I created this little program: def prime(n): if n <= 1: return False for i in range(2, n -1): if n%i == 0: return False return True It's right? all right? 😊
5th Oct 2018, 2:14 PM
<StraMa/Design>
<StraMa/Design> - avatar
+ 5
Kishalaya Saha rereading it I realized that I was enough range (2, n) but now it was tarfi 😂😂 I thank you again infinitely now I play a little with the code and if I develop something interesting I'll show you! 👍😊 thank you very much again! 👊📚😊
5th Oct 2018, 2:50 PM
<StraMa/Design>
<StraMa/Design> - avatar
+ 4
Kishalaya Saha I'm sure!! 👊 Thank you so much !! 😉
5th Oct 2018, 3:07 PM
<StraMa/Design>
<StraMa/Design> - avatar
+ 3
Excellent! 😊 I hope you'll be able to get started on the those prime-related challenges now. If you have more questions, we'll be happy to help you out!
5th Oct 2018, 3:03 PM
Kishalaya Saha
Kishalaya Saha - avatar
+ 2
Kishalaya Saha I modified the algorithm a little bit 😊 what do you think? 😉👊 https://code.sololearn.com/c83aJeiFtrIh/?ref=app
6th Oct 2018, 9:47 PM
<StraMa/Design>
<StraMa/Design> - avatar
+ 1
Yes, your function is flawless! Well done! 👍👏 One small remark: In my pseudocode, I iterated i from 2 to n-1. But range(2, n-1) would give you numbers from 2 to n-2. The last number, n-1 is not included. So to translate the pseudocode correctly, we'd have to do range(2, n). BUT... range(2, n-1) is also fine! The code would work perfectly even if we just test the numbers between 2 and n-2. (In fact, a little more thinking tells us if n is not prime, it should have a divisor between 2 and the square root of n. So actually it is enough to check with those numbers. If you want to know more about this and other ways to optimize it, let me know. But either way, what you did is perfectly fine!)
5th Oct 2018, 2:42 PM
Kishalaya Saha
Kishalaya Saha - avatar
0
def isPrime(x): if x < 2: return False elif x == 2: return True elif x % 2 == 0: return False for n in range(3, int(x**0.5) + 1, 2): if x % n == 0: return False return True
27th Jan 2024, 5:54 AM
SK MASUM ALI
SK MASUM ALI - avatar