Prime Number

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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 😊

Answer 4

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? 😊

Answer 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! 👊📚😊

Answer 6

Kishalaya Saha I'm sure!! 👊 Thank you so much !! 😉

Answer 7

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!

Answer 8

Kishalaya Saha I modified the algorithm a little bit 😊 what do you think? 😉👊

https://code.sololearn.com/c83aJeiFtrIh/?ref=app

Answer 9

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

Answer 10

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