Enjoy an ad free experience by logging in. Not a member yet? Register.

Results 1 to 9 of 9
Thread: C++ Challenge!

10192007, 01:32 AM #1
 Join Date
 Jul 2007
 Posts
 67
 Thanks
 0
 Thanked 0 Times in 0 Posts
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.
10192007, 07:38 AM
#2
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.
10202007, 11:22 PM
#3
 Join Date
 Apr 2007
 Location
 U.S.A
 Posts
 129
 Thanks
 1
 Thanked 0 Times in 0 Posts
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)
Last edited by awsomejoe23; 10202007 at 11:46 PM.
10212007, 09:22 AM
#4
 Join Date
 Jun 2002
 Location
 USA
 Posts
 9,074
 Thanks
 1
 Thanked 328 Times in 324 Posts
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.
OracleGuy
10212007, 03:39 PM
#5
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
Eratosthenes < that one doesn't seem feasible tho..
Interesting Applet
"To iterate is human, to recurse divine." L. Peter Deutsch
10212007, 04:44 PM
#6
 Join Date
 Mar 2007
 Location
 Florida, USA
 Posts
 3,647
 Thanks
 2
 Thanked 406 Times in 398 Posts
Or the student didn't find it, and the OP wants that gift card.
10212007, 07:32 PM
#7
 Join Date
 Aug 2003
 Location
 One step ahead of you.
 Posts
 2,815
 Thanks
 0
 Thanked 3 Times in 3 Posts
I'm not sure if this was any help, but I hope it didn't make you stupider.
Experience is something you get just after you really need it.
PHP Installation Guide Feedback welcome.
10212007, 08:25 PM
#8
 Join Date
 Aug 2003
 Location
 One step ahead of you.
 Posts
 2,815
 Thanks
 0
 Thanked 3 Times in 3 Posts
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.
I'm not sure if this was any help, but I hope it didn't make you stupider.
Experience is something you get just after you really need it.
PHP Installation Guide Feedback welcome.
10212007, 10:09 PM
#9