Results 1 to 6 of 6

Math Help - Prime factoring a large number.

  1. #1
    Newbie
    Joined
    Sep 2011
    Posts
    3

    Prime factoring a large number.

    Is there a theorem or algorithm which would help me factor a 6-digit number into primes? I need to do it by hand (of course I can use a calculator, but not factoring programs or something like that).
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    11,589
    Thanks
    1444

    Re: Prime factoring a large number.

    Quote Originally Posted by Gytax View Post
    Is there a theorem or algorithm which would help me factor a 6-digit number into primes? I need to do it by hand (of course I can use a calculator, but not factoring programs or something like that).
    Have you ever heard of a factor tree?

    Prime Factorization
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Sep 2011
    Posts
    3

    Re: Prime factoring a large number.

    Quote Originally Posted by Prove It View Post
    Have you ever heard of a factor tree?

    Prime Factorization
    I can't just keep checking if that 6-digit number is divisible by every prime or other number up to 800. The first few primes don't work so I need something smarter to do. Any ideas?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,705
    Thanks
    1637
    Awards
    1

    Re: Prime factoring a large number.

    Quote Originally Posted by Gytax View Post
    I can't just keep checking if that 6-digit number is divisible by every prime or other number up to 800. The first few primes don't work so I need something smarter to do. Any ideas?
    You said that you cannot use a calculator.
    Then it has to be do 'by hand'
    Each time you find a factor, that reduces the problem.
    If the number is even, then 2 is a factor. Deduce it to half the number.
    In each reduction, you need only test primes up to the square root of the reduced number.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Sep 2011
    Posts
    3

    Re: Prime factoring a large number.

    I said that I can use a calculator, just not WolframAlpha via computer or that kind of solvers. That 6-digit is the product of two 3-digit numbers so I can't just check so much numbers.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4

    Re: Prime factoring a large number.

    Quote Originally Posted by Gytax View Post
    I can't just keep checking if that 6-digit number is divisible by every prime or other number up to 800. The first few primes don't work so I need something smarter to do. Any ideas?
    As a composite number N has a prime divisor \le \sqrt{N}, for six digit numbers you only need check primes up to \sqrt{N} and since

    \pi(N)\sim \frac{N}{\ln(N)}

    the number of primes less than \sqrt(N) is \sim \le \frac{1000}{\ln(1000)}\approx 145.

    So in general that is less than 145 trial divisions to find the first prime divisor, and every thing accelerates from there..

    (There are in fact 168 primes less than the 1000)

    CB
    Last edited by CaptainBlack; September 10th 2011 at 04:40 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Prove a large number is prime
    Posted in the Number Theory Forum
    Replies: 9
    Last Post: February 1st 2011, 10:17 PM
  2. Replies: 13
    Last Post: December 19th 2010, 03:09 PM
  3. Comparing large prime powers.
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: November 9th 2010, 07:08 AM
  4. Factoring large primes
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 5th 2009, 03:19 AM
  5. Generating Large Prime Numbers
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: July 26th 2009, 02:08 PM

Search Tags


/mathhelpforum @mathhelpforum