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

Thread: C++ Challenge!

  1. #1
    New Coder
    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.

  • #2
    Regular Coder ralph l mayo's Avatar
    Join Date
    Nov 2005
    Posts
    951
    Thanks
    1
    Thanked 31 Times in 29 Posts
    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.

  • #3
    Regular Coder
    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 (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)
    Last edited by awsomejoe23; 10-21-2007 at 12:46 AM.

  • #4
    Rockstar Coder
    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

  • #5
    Regular Coder Aradon's Avatar
    Join Date
    Jun 2005
    Location
    USA
    Posts
    734
    Thanks
    0
    Thanked 20 Times in 19 Posts
    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
    "To iterate is human, to recurse divine." -L. Peter Deutsch

  • #6
    Super Moderator Inigoesdr's Avatar
    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.

  • #7
    Senior Coder
    Join Date
    Aug 2003
    Location
    One step ahead of you.
    Posts
    2,815
    Thanks
    0
    Thanked 3 Times in 3 Posts
    Quote Originally Posted by ralph l mayo View Post
    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.
    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.

  • #8
    Senior Coder
    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.

  • #9
    Regular Coder ralph l mayo's Avatar
    Join Date
    Nov 2005
    Posts
    951
    Thanks
    1
    Thanked 31 Times in 29 Posts
    Quote Originally Posted by marek_mar View Post
    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
    •