Math Is Fun Forum

  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2007-03-15 05:35:59

Stanley_Marsh
Member
Registered: 2006-12-13
Posts: 345

Is there any shortcut?

The unique factorization theorem says that every positive integer number greater than 1 can be written in only one way as a product of prime numbers.

   Is there a way I can find those prime faster? so I don't have to try all the primes less than that integer.


Numbers are the essence of the Universe

Offline

#2 2007-03-15 06:41:23

pi man
Member
Registered: 2006-07-06
Posts: 251

Re: Is there any shortcut?

There aren't any shortcuts that I know of.   Just start with the smallest primes (2, 3, 5, 7, 11) because they're the easiest.    Once you get to the point where the prime numbers are greater the square root of the number you're factoring, you can quit.   For example, if you're factoring 401 you don't have to try any factors greater than 21.

Offline

#3 2007-03-15 07:07:24

mathsyperson
Moderator
Registered: 2005-06-22
Posts: 4,900

Re: Is there any shortcut?

Yes, there's no easier way than just trying all the primes. That fact is exploited by security systems and encryption and stuff.


Why did the vector cross the road?
It wanted to be normal.

Offline

#4 2007-03-15 10:01:16

Ricky
Moderator
Registered: 2005-12-04
Posts: 3,791

Re: Is there any shortcut?

There is a small shortcut you can use.  Here is the algorithm.

Let n be some integer.  Start at p = 2.

While n != 1
   If p | n, then
      while p | n
         "print" p
         n = n/p
      End While
   End If
   p = next_prime(p)
End While.

We can divide n by a the prime we find because we know that n is a product of distinct primes, and so once we find one, we can "take it out" of n.

It won't do too much, but it will make division easier.


"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

Offline

#5 2007-03-15 10:18:38

Stanley_Marsh
Member
Registered: 2006-12-13
Posts: 345

Re: Is there any shortcut?

Lol~ that's programming method ,right?


Numbers are the essence of the Universe

Offline

#6 2007-03-15 13:48:14

Ricky
Moderator
Registered: 2005-12-04
Posts: 3,791

Re: Is there any shortcut?

Yes, but you can do it by hand as well.  There are many algorithms in number theory of this nature.


"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

Offline

#7 2007-03-15 15:02:09

Stanley_Marsh
Member
Registered: 2006-12-13
Posts: 345

Re: Is there any shortcut?

We can divide n by a the prime we find because we know that n is a product of distinct primes, and so once we find one, we can "take it out" of n.

but if a number is the product of two 22 digits primes , then ....

If I can find a method ~WOW~lol ~jk


Numbers are the essence of the Universe

Offline

#8 2007-03-15 15:33:26

Ricky
Moderator
Registered: 2005-12-04
Posts: 3,791

Re: Is there any shortcut?

but if a number is the product of two 22 digits primes , then ....

There is no easy way to do that.  At least I hope there isn't.  Otherwise, many security systems will break down.  Factoring the prime factors of a number is computationally difficult for high primes, and this is heavily used in cryptography to make codes which would take years and years to break.


"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

Offline

#9 2007-03-15 15:38:16

Stanley_Marsh
Member
Registered: 2006-12-13
Posts: 345

Re: Is there any shortcut?

Yah~true , that will bring a huge revolution ~hehe and turbulence


Numbers are the essence of the Universe

Offline

Board footer

Powered by FluxBB