Hello and welcome to our community! Is this your first visit?
Enjoy an ad free experience by logging in. Not a member yet? Register.

1. ## C++ Challenge!

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.

• 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.

• 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 (6n-1)."
You could do
(6n +or- 1) * (6x +or-1) = 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)

• 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.

• It's possible that the student used the theory, k-almost-prime 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
Eratosthenes <-- that one doesn't seem feasible tho..

Interesting Applet

• Or the student didn't find it, and the OP wants that gift card.

• Originally Posted by ralph l mayo
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.

• 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.

• Originally Posted by marek_mar
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 :]

•

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•