Question

what is the prime factorization of 3000056

Answer 1

Whenever you have to factorize an even number, find all the factors of two before starting other tests.
To give you a kickstart, I'd begin with:
\(3000056=2^3*375007\)
Now you would have to do divisibility tests for 3,5,7,11,13,17,19,23,29,31,37... (primes)
If you don't know the divisibility tests, post. Beyond 13 you would have to divide each time to see if there is any remainder.

Answer 2

To check your answer
http://www.wolframalpha.com/input/?i=factor+3000056

Answer 3

There is an interesting method to factor huge odd numbers, let me see if i get this correctly.. .we start with :
\[375007 = x^2-y^2\]

Answer 4

try
6064
6033

Answer 5

Right, but its hard to find them

Answer 6

\[375007 = x^2-y^2 = (x+y)(x-y)\]
you're done once you found the x and y values

did u use pell's equation or something to find those values ?

Answer 7

thats why we have hmm the uncivilized Sieve of Eratosthenes

Answer 8

this method is called Fermat-Kraitchik factorization

supposed to be superior to sieve of eratosthenes

Answer 9

see for sieve we have testes up to 612
for Fermat i can see 6033
so i guess its a bit miss when u have huge number that have only 2 primes factors other wise it works nice

Answer 10

Fermat's should work very well for primes for breaking codes, because the factors are usually close together to make huge factors.

Answer 11

Yeah Fermat-Kraitchik factorization method works nicely when the factors are close together

Answer 12

but in the present example the number factors to 31*12097 and the method is no longer efficient

Answer 13

31 is a reasonable number for trial division.