View Full Version : C++ Challenge!
MindTheGap 10192007, 02:32 AM This is a really fun problem. My teacher assigned it to us last week and the first person that got it correct got an iTunes gift card.
Somebody already won, so I thought I'd post the problem here to see if you guys can get it!
The number below is a composite. It is the product of two prime numbers. Just like 21 is equal to 7 times 3, the number below is equal to the product of two primes.
1,435,334,297,627,885,237,510,222,145,546,396,275,688,036,595,057,651,576,302,853
Your job is to find the two primes that when multiplied, the result is the above number.
ralph l mayo 10192007, 08:38 AM Someone got it? Did they use a quantum computer? I was under the impression that prime factorization for numbers that large was computationally infeasible. Unless I'm missing something about this particular number, which is a likely scenario.
awsomejoe23 10212007, 12:22 AM I'm sure they could have a simple algorithm that utilized some sort of numerical pattern in in the product of prime numbers.
For example, just now thinking about it
9 * x
first_digit =
x  1
second_digit =
the difference between (x and 9) +1
Or at least I think so, just came up with that, :)
My point being you could reverse that, as well as any formula for multiplying 2 prime numbers.
Joe
EDIT: looked around real quick, and I found this
"all prime numbers can be written as (6n+1) or (6n1)."
You could do
(6n +or 1) * (6x +or1) = 1,435,334,297,627,885,237,510,222,145,546,396,275,688,036,595,057,651,576,302,853
then use foil, to get it down, then use simple substitution, or elimination to find the answer. (but that would take too long, I would look for some sort of patterns)
oracleguy 10212007, 10:22 AM To find a value of n that met that equation would require a lot of processing power.
I am also curious how this student figured it out.
Aradon 10212007, 04:39 PM It's possible that the student used the theory, kalmostprime in order to make it at least slightly more computably feasible.
There are a couple theories out there on how to get a prime number in a shorter time rather then worrying getting it exactly. A quick google search turned up two for me
Almost Prime (http://en.wikipedia.org/wiki/Almost_prime)
Eratosthenes (http://www.math.utah.edu/~alfeld/Eratosthenes.html) < that one doesn't seem feasible tho..
Interesting Applet (http://www.cryptographic.co.uk/factorise.html)
Inigoesdr 10212007, 05:44 PM Or the student didn't find it, and the OP wants that gift card. :D
marek_mar 10212007, 08:32 PM Someone got it? Did they use a quantum computer? I was under the impression that prime factorization for numbers that large was computationally infeasible. Unless I'm missing something about this particular number, which is a likely scenario.
That number is not really that big. It's "only" 200 bits. The smallest number to factorize in the RSA factoring challenge had 330 bits and was factorized in 1991.
marek_mar 10212007, 09:25 PM Actually I've already found them. It took my Core 2 Duo 5 minutes:
1159604909814835281776480024219 * 1237778734359686514332712408287 = 1435334297627885237510222145546396275688036595057651576302853
Though I didn't write the thing that actually did it.
ralph l mayo 10212007, 11:09 PM That number is not really that big. It's "only" 200 bits. The smallest number to factorize in the RSA factoring challenge had 330 bits and was factorized in 1991.
Ah yeah, you're right. It certainly *looks* that big, though :]

