It is very slow because the algorithm is a trial division that doesn't stop at the square root. This contradicts our assumption that C is the smallest divisor of N, so smallest divisors of a number is always a prime. So P|C, but we have C|N => P|N where 1 < P < C. Now C is composite so, it has divisor less than itself but greater than one. Then a number N has a smallest yet composite divisor, say C.
Why smallest divisor(except 1) of a number is a prime ? But since 4 > ceil(sqrt(5))Īnd we can say 5 is a prime without any doubt. Now check prime divisors from 45/3 = 15, but start with 3. Because, Tn/p is also a divisor of Tn and since Tn does not have divisors less than p, Tn/p does not have it too. And once you get a prime divisor p don't start again from 2 for Tn/p. So collect them and they are the prime divisors of Tn.įor better time-complexity, you can check for divisors up to upto ceil(sqrt(Tn)) only, instead of Tn-1.Īnd when you start checking for prime divisor for Tn, you can start with 2. Suppose that is p, find the lowest divisor again for Tn/p and so on. What you can do is find the lowest divisor of Tn. See also a related answer with pseudocode, and another with C code. Integer arithmetics for long long ints should work just fine to find the modulo, and so the smallest multiple in range, when you first start (or resume your work). PrimePi(1048576)=82025 primes is all you need in your core primes list. No need to sort by the multiples' values, the upper bound of core primes' use rises monotonically. The step value is twice p in value, or p offset in the odds-packed sieve array, where the i-th entry stands for the number o + 2i, o being the least odd not below the range start.
For each prime p maintain additional long long int value: its current multiple (starting from the prime's square, of course). Then continue to work by big enough segments that fit in your cache, without adding new primes to the core list.
Pre-calculate your core primes with segmented sieve. That's the minimal optimization you should always use - working with odds only.
0 kommentar(er)
