Tell us what’s happening:
Hello dear friends
For this challenge I used Wilson’s formula to test if an integer is prime or not, and I used function fact for factorial.
So, this code works until number 23, after that it gives wrong results.
I’m sure that the formula works for all integers; because I’ve done some calculations with the Calculator and the formula works.
What do you think the problem is?
Your code so far
function sumPrimes(num) {
var prime = [];
// this code to get the factorial of a number
function fact(num){
var prod = 1;
let i = 1;
while(i<=num){
prod = prod*i;
i++;
}
return prod
}
// I used the Wilson's theorem : f(n) = 2 + (2(n!) mod(n + 1)), n is integer positive
// Wilson said if f(n) = n + 1 than (n+1) is prime eles if f(n) = 2 it isn't
for (let i=1; i<=num; i++){
if ((2+((2*fact(i))%(i+1)))==(i+1)){
prime.push(i+1);
}
}
console.log(prime);
//filter function to get all prime number <= num
var results = prime
.filter(val=>{
return val<=num;
});
//return the sum of all array number
return results.reduce((total, val)=>{
return total+val
})
}
//2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41
console.log(sumPrimes(10));
Your browser information:
User Agent is: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:80.0) Gecko/20100101 Firefox/80.0.
The execution is timing out, and the way FCC’s JS harness works is to just silently break from the loop. Not ideal, but that’s what we’ve got. You need a dynamic computing algorithm like sieve, or memoizing the results of the fact function . It’s one of the hardest, if not the hardest challenge in the curriculum.
The biggest issue is that you are overflowing with fact(). If you check sumPrimes(977), you are way under the target value. This is because comparison is no longer exact once you overflow the max safe integer.
You can repair your factorial function by taking the modulus on each iteration of your loop computing the factorial or by using a BigInt.
Computing the sum as you go instead of making an array of primes
If you are using BigInt, computing the factorial as you go.
Like @chuckadams said though, the absolute fastest approach to this problem will be using the Sieve algorithm. I’ve got a thread around here somewhere with some perf analysis of the Sieve based code if you’re interested.
That said, it is awesome to see a novel approach to this problem on the forum! Nice work!
Spoilers!!! Don't look until your code is fixed!!!
Here is my version of your code with my recommended fixes:
I wrote an isPrime function that will determine that this number 7427466391 is a prime in 20 sec on my I7 machine in the newest Edge browser and the same in chrome but much longer in firefox.
I wrote it the simplest possible way, by dividing by an incrementing value (a++) while the value is less than half of the number under test and the division has a remainder . I guess you would call this a “brute force” method.
It is a reasonable approach for checking the primality of a single number, though you can be much more aggressive with the upper bound on the range of numbers you need to check.
If 2 is not a factor, then num / 2 is not a factor.
If 3 is not a factor, then num / 3 is not a factor.
…
so,
If ? is not a factor, then ? is not a factor an the number is prime.
Using this isPrime function I can solve sum of primes less than half a million in fifteen seconds in a chrome based browser on my I7 machine. I will {when I fell motivated} look to optimize the function. What would be a reasonable goal in terms of execution time, what execution times are you aware of ?
--------------------------------------------------
Summary
- Number of Test Cases : 8
- Runs Per Test Case : 25
--------------------------------------------------
--------------------------------------------------
Test Case 0
--------------------------------------------------
- Problem Values
Num : 5
Result : 10
- Statistics
Average Time : 0.02238163962960243
Minimum Time : 0.006562002003192902
Maximum Time : 0.24678799882531166
Standard Deviation : 0.048446783438661864
Variance : 0.002347090825552601
--------------------------------------------------
--------------------------------------------------
Test Case 1
--------------------------------------------------
- Problem Values
Num : 50
Result : 328
- Statistics
Average Time : 0.017763000428676606
Minimum Time : 0.01085200160741806
Maximum Time : 0.13660000264644623
Standard Deviation : 0.02449551421398306
Variance : 0.000600030216607446
--------------------------------------------------
--------------------------------------------------
Test Case 2
--------------------------------------------------
- Problem Values
Num : 500
Result : 21536
- Statistics
Average Time : 0.07223927974700928
Minimum Time : 0.0566370002925396
Maximum Time : 0.15049299970269203
Standard Deviation : 0.022425811303324508
Variance : 0.0005029170126123173
--------------------------------------------------
--------------------------------------------------
Test Case 3
--------------------------------------------------
- Problem Values
Num : 5000
Result : 1548136
- Statistics
Average Time : 3.7794425602257253
Minimum Time : 0.0437219999730587
Maximum Time : 84.67070099711418
Standard Deviation : 16.52245980120333
Variance : 272.9916778823799
--------------------------------------------------
--------------------------------------------------
Test Case 4
--------------------------------------------------
- Problem Values
Num : 50000
--------------------------------------------------
Summary
- Number of Test Cases : 8
- Runs Per Test Case : 25
--------------------------------------------------
--------------------------------------------------
Test Case 0
--------------------------------------------------
- Problem Values
Num : 5
Result : 10
- Statistics
Average Time : 0.016328599750995636
Minimum Time : 0.006414998322725296
Maximum Time : 0.18041600286960602
Standard Deviation : 0.033737119760613124
Variance : 0.0011381932497419526
--------------------------------------------------
--------------------------------------------------
Test Case 1
--------------------------------------------------
- Problem Values
Num : 50
Result : 328
- Statistics
Average Time : 0.013075799793004989
Minimum Time : 0.011069998145103455
Maximum Time : 0.03007100149989128
Standard Deviation : 0.003735707063334401
Variance : 0.000013955507263046534
--------------------------------------------------
--------------------------------------------------
Test Case 2
--------------------------------------------------
- Problem Values
Num : 500
Result : 21536
- Statistics
Average Time : 0.059613520205020906
Minimum Time : 0.04412900283932686
Maximum Time : 0.11219599843025208
Standard Deviation : 0.01503463773500291
Variance : 0.0002260403318227734
--------------------------------------------------
--------------------------------------------------
Test Case 3
--------------------------------------------------
- Problem Values
Num : 5000
Result : 1548136
- Statistics
Average Time : 0.4202562004327774
Minimum Time : 0.03033200278878212
Maximum Time : 1.9804480001330376
Standard Deviation : 0.49184938081103846
Variance : 0.24191581340420193
--------------------------------------------------
--------------------------------------------------
Test Case 4
--------------------------------------------------
- Problem Values
Num : 50000
Result : 121013308
- Statistics
Average Time : 3.7944940401613714
Minimum Time : 0.4456310011446476
Maximum Time : 74.0387319996953
Standard Deviation : 14.3777100244653
Variance : 206.71854554760995
--------------------------------------------------
--------------------------------------------------
Test Case 5
--------------------------------------------------
- Problem Values
Num : 500000
Result : 9914236195
- Statistics
Average Time : 15.74744927972555
Minimum Time : 5.7551060020923615
Maximum Time : 66.41429599747062
Standard Deviation : 17.970264238023965
Variance : 322.930396784403
--------------------------------------------------
--------------------------------------------------
Test Case 6
--------------------------------------------------
- Problem Values
Num : 5000000
Result : 838596693108
- Statistics
Average Time : 199.7129411199689
Minimum Time : 137.23859500139952
Maximum Time : 254.57499299943447
Standard Deviation : 19.00734407318568
Variance : 361.27912871646686
--------------------------------------------------
--------------------------------------------------
Test Case 7
--------------------------------------------------
- Problem Values
Num : 50000000
Result : 72619548630277
- Statistics
Average Time : 2568.9573716001214
Minimum Time : 2327.0637709982693
Maximum Time : 3240.5762819983065
Standard Deviation : 202.72765944216144
Variance : 41098.503902896984
--------------------------------------------------
Thanks for your response, and don’t worry, I have a problem is that I can’t look at the solution without being stuck for a long time lol ^^
What do you mean by Sieve algorithm?
There is a good Wikipedia article on the sieve (I’d Google it, but I’m on my phone). The basic idea is that you make you make an array of length num and fill every single entry with ‘true’. Then you start with 2 and mark every multiple of a prime number as ‘false’. So 4, 6, 8,… are marked false. 3 would not be marked false, so you go mark every multiple of 3 as false. And so on throughout the array.
I am really really glad I read this thread!!
all I did to my code was “Remember”
the previous value and use it in the current
calculation. My routine went from three lines to five lines, now I can confirm that 7427466391 is prime in a flash.
stored it in a var then added that var into next calculation
it gets really “aggressive” toward the end
this explains it all …
If 2 is not a factor, then num / 2 is not a factor.
If 3 is not a factor, then num / 3 is not a factor.
…
so,
If ? is not a factor, then ? is not a factor an the number is prime.
