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.
Anyway, sorry about the inconvenience. Happy reading.
--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
New email address: mehgcap@xxxxxxxxx
----- 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
New email address: mehgcap@xxxxxxxxx
__________
View the list's information and change your settings at
//www.freelists.org/list/programmingblind
__________
View the list's information and change your settings at
//www.freelists.org/list/programmingblind
__________
View the list's information and change your settings at
//www.freelists.org/list/programmingblind
__________
View the list's information and change your settings at
//www.freelists.org/list/programmingblind
