DEV Community

loading...
Cover image for A Simple Method To Finding Prime Numbers.

A Simple Method To Finding Prime Numbers.

seanolad profile image Sean ・3 min read

Intro

In this post I'm going to go over how to create a function that will determine whether a number is prime and a function that prints all the prime numbers under it(and the number itself if it's a prime number).

Okay Prime Numbers

This task might seem a little difficult for beginners to programming, but it actually just requires a little thinking and that's it, and a teeny tiny bit of math.

I'm not a math genius so I might not get it.

Trust me, it's a lot easier than you think.

How Do we Do This?

Every prime number except for 2 and 3 follow a specific pattern. the number above or below it is divisible by 6.

Yeah, but can't normal numbers fall under this?

Sadly, yes.

So not all prime numbers follow this rule?

No, all prime numbers do follow this rule, but every once in a while other numbers that aren't prime can have this trait.

Which ones?

Well, 25 isn't a prime but 24 is divisible by 6. So that's one that's early on.

So, how do we get rid of them?

Based on my math it seems that all of these stragglers are powers of 2, 3, 5, 7, and 11.

What about the other prime numbers?

We don't need to worry about them, the cross filtering of the 6 rule and the power rule will create an exact method.

I don't understand.

In simple terms all we have to do is make two functions, one for the 6 rule and another for the power rule(there are other ways to get prime numbers, this isn't the only way).
Let me show you what it'd look like in a few languages.

Wow, that was easy!

I know!

Generating prime numbers

So, now that we know know how to determine whether the input is a valid prime number we can use the functions just presented to generate prime numbers.

Hold on, our functions only return a boolean value how does that help?

Quick recap: boolean logic is for making decisions(that's how if statements work), so if a number is prime both functions will return true.

So?

So we can iterate it over each number in the given range and add it to a list. Once that's done we can print each number to see the results.

Okay, but how do we do that?

I'll show you.

Okay what's going on?

I used two different methods for the all 4 languages. In python, ruby, and javascript I made a list using a range from 1 to the given number and for each number i checked if it was prime, if findingPrime/findprime/finding_prime returns true and is_power/isPower/ispower returns true then the number is printed. If not it's skipped.

Okay, what about the second method?

For C++ I made a while loop and called the findingprimes function and the ispower function on the given number, if it's prime it gets printed if not it is skipped. Then "num" is decreased by one and the proccess repeats untill num is equal to zero.

Hope you learned something!

Discussion (9)

Collapse
cuotos profile image
Dan P • Edited

As Thorsten already pointed out, (25 - 1) % 6 == 0, but 25 is also divisible by 5, therefore not a prime.

But that said, I like the article and you are clearly passionate about learning. I would recommend you take this opportunity to start looking at unit testing of code if you haven't already. Testing your code against a KNOWN set of correct / incorrect results. For example (I've done this in Golang, but with your grasp of different languages, the logic should make sense)

play.golang.org/p/ouuBBadcqHn

Quick and dirty, but for numbers up to 500 compare your logic to a KNOWN list (which was pre generated). This gives you confidence your code works.

My other MINOR feedback point would be the names of functions, they should clearly tell users what it does. Especially in Ruby that allows question marks in the names, and by convention should be used on functions that return boolean.

finding_primes(num) bool
vs
is_prime?(num) bool

It's a little thing that your future colleagues (and your future self when you look at old code), will thank you for.

Collapse
seanolad profile image
Sean Author

Okay, I'll remember that. Thanks man.

Collapse
cat profile image
Cat

This is pretty great, and I liked how you covered several programming languages!
For best practices in JS, however, it's best to use the strict comparison ("===") operator, just because a ton of things can slip through the cracks when using "==".

Collapse
seanolad profile image
Collapse
thorstenhirsch profile image
Thorsten Hirsch

25 is not a prime.

Collapse
seanolad profile image
Sean Author

I'll make an adjustment to my method

Collapse
seanolad profile image
Sean Author

I updated the post

Collapse
thorstenhirsch profile image
Thorsten Hirsch

Unfortunately I‘ve found another non-prime, that should have been prime according to your new algorithm: 299. It‘s a multiple of 13.

Collapse
seanolad profile image
Sean Author

Yeah, I wrote a different method and posted it. The name of the post is Generating Prime Numbers: Reloaded.

Forem Open with the Forem app