prime factorization of two large numbers - Printable Version +- Python Forum (https://python-forum.io) +-- Forum: Python Coding (https://python-forum.io/forum-7.html) +--- Forum: Homework (https://python-forum.io/forum-9.html) +--- Thread: prime factorization of two large numbers (/thread-4522.html) |
prime factorization of two large numbers - pyJim - Aug-23-2017 I'm stuck on a part of my assignment. The last two numbers in my output are missing a number on the right hand side of the = sign so that when the three are multiplied they equal the number on the left hand side of the = sign. I know what the missing numbers are but I'm unsure how to modify the code so that the output looks like all the other factored numbers (a "check" instead of an "oops"). I think it could possibly be done using integer division and the variable n inside one of the functions, but again I'm not sure how. Any guidance would be greatly appreciated. Thanks! __author__ = 'pyJim' import time def sieve(n=1000000): multiples = set() primes = [2] for i in range(3, n, 2): if i not in multiples: primes.append(i) multiples.update(m for m in range(i*i, n+1, i)) print('number of prime numbers < {:,d} is {:,d}'.format(n,len(primes))) return primes def largestPrimeFactor(n, primes): for i in primes[::-1]: if n % i == 0: return i return -1 def primeFactors(n, primes): factors = [largestPrimeFactor(n, primes)] r = n i = 0 while factors[i] > 0: r = r // factors [i] i += 1 factors.append(largestPrimeFactor(r, primes)) return factors[:-1] def main(): primes = sieve(int(1e7)) with open('data1.dat', 'r', encoding='UTF-8') as f: for line in f.readlines(): n = int(line) factors = primeFactors(n, primes) p = 1 for y in factors: p *= y if factors[0] == n: print('{:,d} is prime'.format(n)) else: print('{:,d} = {:s}'.format(n, " * ".join('{:,}'.format(f) for f in factors if f != -1))) print('{} = {:,d} {}'.format(' '*len('{:,d}'.format(n)), p, 'check' if n == p else 'oops')) if __name__ == '__main__': main() [/i][/i]
RE: prime factorization of two large numbers - micseydel - Aug-23-2017 For your first oops, 11 and 71 are valid components to the prime, which leaves you with 129321228041, which is itself prime and also much larger than your sieve. RE: prime factorization of two large numbers - pyJim - Aug-24-2017 I figured out a solution to my first question, now I have another. If the number has no prime factors I need the program to output this: 23 is prime The line containing = 23 check needs to be removed completely. My best guess is that this occurs in the final if/else print statements because when I comment out else I get 23 is prime, but the problem with that is it won't output the rest of the factored numbers in the list that follow, as is a required by the assignment. I've tried to using strip() but so far has only resulted in errors. Any feedback is always appreciated. Thanks! |