Re: prime factors shortcut question
- From: "qubit" <lauraeaves@xxxxxxxxx>
- To: <programmingblind@xxxxxxxxxxxxx>
- Date: Sat, 10 Oct 2009 18:23:48 -0500
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
New email address: mehgcap@xxxxxxxxx
----- 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
> New email address: mehgcap@xxxxxxxxx
> ----- 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.
>>
>> 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
>>
>
> __________
> 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
Other related posts:
