Wilson's formula to test prime number

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.

Challenge: Sum All Primes

Link to the challenge:

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.

3 Likes

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.

You can also improve your performance by

  1. Using this version of Wilson’s Theorem

  2. Computing the sum as you go instead of making an array of primes

  3. 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:

https://repl.it/repls/DimpledPeskyProtocol#index.js

1 Like

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.

2 Likes

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 ?

My solution, for sumPrimes(500000), provides this runtime and result:
image

1 Like

Best I’ve got is below (time measured in ms).

Timing Results
--------------------------------------------------
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
--------------------------------------------------

This probably means my solution errors out :sweat_smile:

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.

Edit: Wikipedia article

1 Like

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.

for(i=0;i<100000000;i++)
isPrime(7427466391)
alert('done')

18 seconds

so the code got over a hundred million times faster

What do you mean by remember?

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.

I feel like perhaps we are thinking about slightly different things?

my comment there was to say that you need to at most check sqrt(num) to know if num is prime.

Storing the primes and only dividing by them is a different, but related, optimization.

Ultimately, if you are starting with no primes the fastest solution to this challenge will be a Seive.