factorization
Java Display the Prime Factorization of a number
You are almost there! Move the if-continue block outside the for loop. Otherwise, it “continues” the inner-most loop, rather than the one you intended. while (number % i == 0) { number /= i; count++; } if (count == 0) { continue; } System.out.println(i+ “**” + count); Alternatively, you could enclose the System.out.println call in … Read more
Finding largest prime number out of 600851475143?
Not only does your prime checking function always return false; even if it were functioning properly, your main loop does not seek the input number’s factors at all, but rather just the largest prime smaller or equal to it. In pseudocode, your code is equivalent to: foo(n): x := 0 ; foreach d from 1 … Read more
What is the fastest integer factorization algorithm?
Pulled directly from my answer to this other question. The method will work, but will be slow. “How big are your numbers?” determines the method to use: Less than 2^16 or so: Lookup table. Less than 2^70 or so: Richard Brent’s modification of Pollard’s rho algorithm. Less than 10^50: Lenstra elliptic curve factorization Less than … Read more
What is the most efficient way of finding all the factors of a number in Python?
from functools import reduce def factors(n): return set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))) This will return all of the factors, very quickly, of a number n. Why square root as the upper limit? sqrt(x) * sqrt(x) = x. So if the two factors are the … Read more