int a, b; Console.WriteLine(“Please enter your integer: “); a = int.Parse(Console.ReadLine()); for (b = 2; a > 1; b++) if (a % b == 0) { int x = 0; while (a % b == 0) { a /= b; x++; } Console.WriteLine($”{b} is a prime factor {x} times!”); } Console.WriteLine(“Th-Th-Th-Th-Th-… That’s all, folks!”);
A simple trial division: def primes(n): primfac = [] d = 2 while d*d <= n: while (n % d) == 0: primfac.append(d) # supposing you want multiple factors repeated n //= d d += 1 if n > 1: primfac.append(n) return primfac with O(sqrt(n)) complexity (worst case). You can easily improve it by special-casing … Read more
If you don’t want to reinvent the wheel, use the library sympy pip install sympy Use the function sympy.ntheory.factorint Given a positive integer n, factorint(n) returns a dict containing the prime factors of n as keys and their respective multiplicities as values. For example: Example: >>> from sympy.ntheory import factorint >>> factorint(10**20+1) {73: 1, 5964848081: … Read more
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
Here’s the best algorithm I know of (in Python) def prime_factors(n): “””Returns all the prime factors of a positive integer””” factors = [] d = 2 while n > 1: while n % d == 0: factors.append(d) n /= d d = d + 1 return factors pfs = prime_factors(1000) largest_prime_factor = max(pfs) # The … Read more
The basic idea of a segmented sieve is to choose the sieving primes less than the square root of n, choose a reasonably large segment size that nevertheless fits in memory, and then sieve each of the segments in turn, starting with the smallest. At the first segment, the smallest multiple of each sieving prime … Read more