search

stevenhalim / cpbook-code

CP4 Free Source Code Project (C++17, Java11, Python3 and OCaml)
2k stars 493 forks source link

Bug in ch5/primes.cpp #62

Closed seffendy closed 4 years ago

seffendy commented 4 years ago

In ch5/primes.cpp -- primeFactors(ll N):

while (PF*PF <= N) {
  while (N%PF == 0) { N /= PF; factors.push_back(PF); }
  PF = primes[++PF_idx];
}

This code might crash due to index-out-of-bound in PF = primes[++PF_idx]. Consider the case when PF_idx = primes.size()-1 (the last prime in primes), then when it goes to the problematic line, PF_idx becomes primes.size() which does not exist in PF.

This bug also happened in other functions as well, i.e., numPF(), numDiffPF(), sumPF(), numDiv(), sumDiv(), EulerPhi().

stevenhalim commented 4 years ago

Eh this is not a bug, it is a feature, I will not change it, go to private discussion

stevenhalim commented 4 years ago

ok, not fully closed, let's discuss again

stevenhalim commented 4 years ago

this is done by now :)