Python Forum
prime factorization of two large numbers
Thread Rating:
  • 1 Vote(s) - 3 Average
  • 1
  • 2
  • 3
  • 4
  • 5
prime factorization of two large numbers
#1
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()
Output:
number of prime numbers < 10,000,000 is 664,579 23 is prime    = 23 check 985,989,664,361 = 89,273 * 65,353 * 13 * 13                 = 985,989,664,361 check 874,789,985,093 = 1,067,063 * 819,811                 = 874,789,985,093 check 629,812,260 = 17 * 11 * 11 * 7 * 5 * 3 * 3 * 3 * 3 * 3 * 3 * 3 * 2 * 2             = 629,812,260 check 87,664,578 = 8,167 * 1,789 * 3 * 2            = 87,664,578 check 9,999,991 is prime           = 9,999,991 check 9,995,139 = 14,423 * 11 * 7 * 3 * 3           = 9,995,139 check 9,990,363 = 3,330,121 * 3           = 9,990,363 check 9,988,453 is prime           = 9,988,453 check 100,999,879,100,021 = 71 * 11                     = 781 oops 59,999,568,001,069,198,950,240,354,291 = 17 * 3                                        = 51 oops
[/i][/i]
Reply


Messages In This Thread
prime factorization of two large numbers - by pyJim - Aug-23-2017, 02:58 AM

Possibly Related Threads…
Thread Author Replies Views Last Post
  Random Generator: From Word to Numbers, from Numbers to n possibles Words Yamiyozx 2 1,519 Jan-02-2023, 05:08 PM
Last Post: deanhystad
  Convert list of numbers to string of numbers kam_uk 5 3,128 Nov-21-2020, 03:10 PM
Last Post: deanhystad
  Prime numbers janoshz 4 2,518 Oct-05-2019, 10:01 AM
Last Post: Preetimishra90
  Prime numbers calculations frequency 3 3,058 Nov-27-2018, 07:07 PM
Last Post: micseydel
  10x10 Array of Prime Numbers smfox2 1 2,602 Sep-03-2018, 12:36 AM
Last Post: ichabod801
  Regular Expressions in Files (find all phone numbers and credit card numbers) Amirsalar 2 4,186 Dec-05-2017, 09:48 AM
Last Post: DeaD_EyE
  PRIME NUMBERS iamnotabot 6 4,737 Sep-17-2017, 04:25 PM
Last Post: iamnotabot

Forum Jump:

User Panel Messages

Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020