Welcome to the Treehouse Community
Want to collaborate on code errors? Have bugs you need feedback on? Looking for an extra set of eyes on your latest project? Get support with fellow developers, designers, and programmers of all backgrounds and skill levels here with the Treehouse Community! While you're at it, check out some resources Treehouse students have shared here.
Looking to learn something new?
Treehouse offers a seven day free trial for new students. Get access to thousands of hours of content and join thousands of Treehouse students and alumni in the community today.
Start your free trial
Ben Son
Courses Plus Student 1,791 PointsIs this the most efficient way for a computer to find Prime Numbers in a range?
This is the method I came up with to find Prime Numbers in a customised range of numbers. This question is not about whether this is the most readable or logical way of doing it (which I hope it is), but whether this is the most time/energy efficient way for the computer to compute this function.
If you have any tips, feel free to comment :)
func searchPrimeNumbers (#from: Int, #to: Int) {
for x in from...to {
if !(x % 2 == 0 || x % 3 == 0 || x % 5 == 0 || x % 7 == 0) ||
(x == 2 || x == 3 || x == 5 || x == 7) {
println(" \(x)")
} else {
println(x)
}
}
}
3 Answers
Derrick McIntosh
2,656 PointsI'm not a math and/or programming expert by any means (yet!), but your code doesn't seem to work for n where n = all positive integers. Unless I'm not reading it right, your code only checks for primes by eliminating numbers wholly divisible by 2, 3, 5, or 7 that are not also 2, 3, 5, or 7. The problem is you can take a number not divisible by these four and square it to obtain a new number that your code would determine to be a prime.
Example:
11 is the next prime number after 7. 11 x 11 = 121. 121 % 2 != 0. 121 % 3 != 0. 121 % 5 != 0. 121 % 7 != 0. 121 is not 2, 3, 5, or 7.
121 therefore passes your prime test and is included any search results.
Here's a link to the Wikipedia page about primality tests.
Here's another link to a Stack Overflow conversation about optimal prime test efficiency for C++.
It seems like the most efficient method depends on your number range. If you aren't searching huge ranges of numbers, you can just include a list of primes to reference. Beyond that it seems you need to delve into probabilistic computing.
EDIT: As Iago notes below, the Sieve of Atkin is probably going to be your best bet as far as an efficient algorithm.
Hope this helps!
Iago Wandalsen Prates
21,699 PointsThat way doesn't even work. It's only going to recognize the multiples of the numbers you know that are prime, but won't get any new primes multiples, like 121.
The most efficient (or one of the most) is the Sieve of Atkin. http://en.wikipedia.org/wiki/Sieve_of_Atkin
Ben Son
Courses Plus Student 1,791 PointsThank you for your answer. I tried to also add the condition || x % sqrt(x) == 0 so I could eliminate numbers that are simply a square of another prime number. But the compiler returns an error when I try to add that piece of code to the condition braces. Any idea how I can add this || x % sqrt(x) == 0 to the !() condition?
Thanks!
chrisp
13,686 PointsJust a thought but what would happen if you did
// in a for loop.
if (x % 2 == 1) {
println(x);
}
Derrick McIntosh
2,656 PointsYou would have a list of odd numbers.
1, 3, 5, 7, 9, 11, 13, etc.
Ben Son
Courses Plus Student 1,791 PointsBen Son
Courses Plus Student 1,791 PointsThank you for your answer. I tried to also add the condition || x % sqrt(x) == 0 so I could eliminate numbers that are simply a square of another prime number. But the compiler returns an error when I try to add that piece of code to the condition braces. Any idea how I can add this || x % sqrt(x) == 0 to the !() condition?
Thanks!
Derrick McIntosh
2,656 PointsDerrick McIntosh
2,656 PointsI haven't yet done any work with iOS, but this still isn't a great way to check for a prime. Using the number 11 again, if we multiply 11 x 11 x 11, we get 1331. This number does not have any lesser number as a whole square root, so it passes your check, but clearly it isn't a prime as it has a whole cube root of 11. You'd have to check for infinite types of roots if you have an input range of infinite whole numbers using your method.
Super slow, super simple method:
Loop through each number n in the range individually with another loop that checks 2 through n/2 as possible factors to very, very slowly identify all possible primes in the range.
Efficient method:
Use an algorithm such as the Sieve of Eratosthenes (simpler version of the Sieve of Atkin) that efficiently culls non-prime numbers in the range, leaving only the primes of the range left. From the Wikipedia article, here is the process for this sieve:
STEP 1 - Create a list of consecutive integers from 2 through n: (2, 3, 4, ..., n). STEP 2 - Initially, let p equal 2, the first prime number. STEP 3 - Starting from p, enumerate its multiples by counting to n in increments of p, and mark them in the list (these will be 2p, 3p, 4p, etc.; the p itself should not be marked). STEP 4 - Find the first number greater than p in the list that is not marked. If there was no such number, stop. Otherwise, let p now equal this new number (which is the next prime), and repeat from step 3.
Link to the article for reference.
You have to remember that a non-prime number can have any set of prime and non-prime numbers as its factors. Your algorithm must iterate over every possible combination of these numbers to ensure you aren't adding non-primes to your search results.
Jason Anello
Courses Plus Student 94,610 PointsJason Anello
Courses Plus Student 94,610 PointsHi Derrick,
In your "super simple method" you only have to go up to the floor of the square root of the number. That cuts back the modulus operations by a pretty good amount.
Ben Son
Courses Plus Student 1,791 PointsBen Son
Courses Plus Student 1,791 PointsDerrick,
thank you very much for your detailed answer! It helped me greatly and motivated me to take more time thinking about how to write my code correctly. Thanks for your effort!!
Derrick McIntosh
2,656 PointsDerrick McIntosh
2,656 PointsJason,
Forgot about the square rule with factoring for prime numbers. Thank you!
Ben,
No problem!