# Re: prime factors shortcut question

• From: "black ares" <matematicianu2003@xxxxxxxxxxx>
• To: <programmingblind@xxxxxxxxxxxxx>
• Date: Sun, 11 Oct 2009 08:42:07 +0300

in programming you proceed even with 13 because the program does not know that 13 is prime. It will try to go one step further and in that moment it will see that it is not posible. so the program will do sqrt(13)=3 and it will try to factorise 13 with 2 and 3 and it will see that none of these is a prime factor of 13 so 13 is prime. I've given a code in a previous message, but it seems that alex didn't see it.

```
```
----- Original Message ----- From: "qubit" <lauraeaves@xxxxxxxxx>
```To: <programmingblind@xxxxxxxxxxxxx>
Sent: Sunday, October 11, 2009 2:23 AM
Subject: Re: prime factors shortcut question

```
no, when you divide 52 by 2 and get 26, then you continue dividing into 26,
```not 52.
You also take floor(sqrt(26)) to get 5 before continuing.
So 52/2 is 26, 26/2 is 13, 13 is prime and greater than 5 so there is no
need to proceed.
HTH
--le

```
----- Original Message ----- From: "Alex Hall" <mehgcap@xxxxxxxxx>
```To: <programmingblind@xxxxxxxxxxxxx>
Sent: Saturday, October 10, 2009 11:31 AM
Subject: Re: prime factors shortcut question

No idea, that is the second time I have done that.
Sorry, but I still am not sure of this. Take 52.
Math.floor(Math.sqrt(52))=7
52/2=26
52/3 fails
52/4=13
52/5 fails
52/6 fails
52/7 fails

So the factors are 2, 13, and 26. Must we then run each factor through to
see if it works?
2 we will not worry about
13's sqrt floor is 3. Nothing except 1 will work, so it is prime.
26=6.
26/2=13
26/3 fails
26/4 fails
26/5 fails
26/6 fails
```
so can we then just throw 26 out if its factors are more than 0, or must we do something else to it? Sorry for all the questions, but I guess it is not
```quite connecting in my head.

Have a great day,
Alex
```
----- Original Message ----- From: "qubit" <lauraeaves@xxxxxxxxx>
```To: <programmingblind@xxxxxxxxxxxxx>
Sent: Saturday, October 10, 2009 11:58 AM
Subject: Re: prime factors shortcut question

```
```random? where do you get random? Replace random with primes and you are
right.
--le

```
----- Original Message ----- From: "Alex Hall" <mehgcap@xxxxxxxxx>
```To: <programmingblind@xxxxxxxxxxxxx>
Sent: Friday, October 09, 2009 11:45 PM
Subject: Re: prime factors shortcut question

Oh, I get it. So floor the sqrt of the number in question, generate all
the
random numbers between 2 (prime 1) and the sqrt floor, then divide each
random into n and see if it works?

Have a great day,
Alex
```
----- Original Message ----- From: "qubit" <lauraeaves@xxxxxxxxx>
```To: <programmingblind@xxxxxxxxxxxxx>
Sent: Saturday, October 10, 2009 12:41 AM
Subject: Re: prime factors shortcut question

```
```no, you are not understanding what I'm saying...
Do the following:

maxfac = floor(sqrt(22))

This yields 4, as you said.

Now walk through all the primes p greater than 1 and less than or equal
to
maxfac.  The only prime is 2, as you said.
But 22 divided by 2 is 11, which is prime.  So it can be added to the
pool
of primes.  Therefore you already know that 11 is prime without actually
doint the math for all the numbers instead of those less than 4.
The algorithm is something like the following pseudo code:

// num = number being factored
max = floor(square root of num)
for each prime between 2 and floor(square root(num)
Doing it any more would give duplicate results.

--le

```
----- Original Message ----- From: "Alex Hall" <mehgcap@xxxxxxxxx>
```To: <programmingblind@xxxxxxxxxxxxx>
Sent: Friday, October 09, 2009 10:56 PM
Subject: Re: prime factors shortcut question

```
I will try it. A question, though: is this only for certain numbers? Look
```at
22 (2*11):
Math.floor(sqrt(22))=4
factors of 4: 2
no 11?

Have a great day,
Alex
```
----- Original Message ----- From: "qubit" <lauraeaves@xxxxxxxxx>
```To: <programmingblind@xxxxxxxxxxxxx>
Sent: Friday, October 09, 2009 11:41 PM
Subject: Re: prime factors shortcut question

```
```take the floor of the square root. --le

```
----- Original Message ----- From: "Alex Hall" <mehgcap@xxxxxxxxx>
```To: "Blind Programming List" <programmingblind@xxxxxxxxxxxxx>
Sent: Friday, October 09, 2009 2:13 PM
Subject: prime factors shortcut question

Hi all,
I am trying to find the prime factors of a massive number, over 600
billion,
in perl (it is just an activity in a class, not an assignment). I know
you
can factor the square root, which is good since I cannot store such a
big
number in a simple scalar in perl, but I run into a problem: the square
root
of my number is not a whole number, but a decimal. Of course, then, any
modulus I try will not work since a decimal mod any whole number will
not
```
return 0. What do I do? Do I get the floor or ceiling of the square root
```operation? Is there another trick? I do not need something vastly
complex
that works for most situations or explains things from a cryptographic
standpoint, all I need is what to do with my decimal square root so
modding
works and gives me factors. Thanks for any help!

Have a great day,
Alex

__________
View the list's information and change your settings at
http://www.freelists.org/list/programmingblind

__________
View the list's information and change your settings at
http://www.freelists.org/list/programmingblind

```
```
__________
View the list's information and change your settings at
http://www.freelists.org/list/programmingblind

__________
View the list's information and change your settings at
http://www.freelists.org/list/programmingblind

```
```
__________
View the list's information and change your settings at
http://www.freelists.org/list/programmingblind

__________
View the list's information and change your settings at
http://www.freelists.org/list/programmingblind

```
```
__________
View the list's information and change your settings at
http://www.freelists.org/list/programmingblind

__________
View the list's information and change your settings at
http://www.freelists.org/list/programmingblind

```
```
__________
```
View the list's information and change your settings at http://www.freelists.org/list/programmingblind
```
```