script type="text/javascript">
function showPrimes(limit){
for(let number= 2; number<= limit; ++number){
let isPrime = true;
}
}
</script>
Above r the code I am currently working on so far. Not sure how to continue.
Hi,
Like this:
const isPrime = num => {
for(let i = 2, s = Math.sqrt(num); i <= s; i++){
if(num % i === 0) return false;
}
return num > 1;
}
const logPrimes = num => {
for (let i = num; i > 0; i--){
if(isPrime(i)) console.log(i);
}
}
logPrimes(10);
// 7, 5, 3, 2
I’m assuming you know how to work out if a number is prime. The only slightly confusing bit is that you only need to check up to a number’s square root to see if it is prime.
Here is a good explanation of why that is:
Apart from that, if anything is unclear, let me know.
I’d also be interested to hear if anyone has a different solution.
@James_Hibbard Posted the same stackoverflow link about a week ago, on another forum 
Can’t take credit for this one and maybe a bit cryptic.
const isPrime = num => num > 1 && [2, 3, 5, 7].every(i => num === i || num % i)
num > 1 is larger than 1
num === i is there to make sure 2,3,5 and 7 always evaluate to true. 2 % 2, 3 % 3 would return remainder 0 or false which we don’t want
num % i will handle the rest of the numbers e.g.
11 % 2 -> remainder 1 true
11 % 3 -> remainder 2 true
11 % 5 -> remainder 1 true
11 % 7 -> remainder 4 true
is prime
(Warning: Contains maths.)
it’s a better shorthand, to be sure, but you’ll need a way of generating the divisors - which… by definition, is the answer to a subquestion, without the actual number being asked about, so eventually, you’re building a rainbow table.
^this array. If i gave you 100 as the limit, the array would have to be [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97] which… coincidentally is also the answer to the problem, because 100 is not prime.
In actuality, you’d still only need the array up to the square root of the answer - once again it may not seem logical as to why, but consider 25, after a brief math break…
x * y = j will break the ‘primeness’ of the number j (given j, x and y to be positive integers, naturally.). Multiplication is communitive, so x * y = y * x. Thus 40 = 4 * 10 = 10 * 4. How ‘high’ do you have to go with the lower number in order to make sure you’ve found all possible x * y pairings? well, the point at which the low number becomes the high number. Which would be when they equal each other. x = y. which makes x * y = x^2. To solve j = x^2, you would take the square root of both sides. So the highest value you would need to check is x = sqrt(j).
Okay. Back to 25, and then 100.
We could check all possible divisors of 25 less than the square root of it. 2,3,4,5.
But… do we need to check 4? If 2 was a no, then 4 will also be a no, because 4 is itself, 2 * 2. So we don’t really need to check 4.
The important thing to note here is that we don’t need to check 4, because it’s made up of things smaller than 4.
These are called Prime Factors, because… they’re all prime numbers.
Take 100.
2,3,4,5,6,7,8,9,10.
What do we need to check?
2
3
Don’t need 4, that was checked by 2.
5.
Don’t need 6, that was checked by both 2 and 3.
7
Don’t need 8, back to the 2’s.
Don’t need 9, that’s 3’s.
Don’t need 10, that’s 2 and 5.
So in truth, 2,3,5,7, is enough to check every number up to 100. But what have we actually done there? In order to find the simplest set of things-we-need-to-check for all numbers less than 100… we’ve found the set of primes less than the square root of 100. But our original problem was finding the set of prime numbers less than a target… ah. we’re walking in circles!
Generalized: The values that need to be tested for the primeness of a number is the set of primes less than or equal to the square root of the target number. Which actually means, for your example of 11, all you mathematically need is:
const isPrime = num => num > 1 && [2, 3].every(i => num === i || num % i)
Effectively, the problem is:
const isPrime = num => num > 1 && getPrimes(Math.sqrt(num)).every(i => num === i || num % i)
meaning… in a way… i’m recursing your solution?
WOW, some food for thought there @m_hutley.
It was a 2.00 am response, so missed that salient point.
Thank you for the detailed breakdown, much appreciated.
edit:
The thought of introducing the Math.sqrt into it hadn’t escaped me, but just couldn’t put the pieces together.
I’m also wondering if this problem is a candidate for memoization?
Apologies to the OP, if I have taken this off track.
This topic was automatically closed 91 days after the last reply. New replies are no longer allowed.