Re: prime factors shortcut question
- From: "qubit" <lauraeaves@xxxxxxxxx>
- To: <programmingblind@xxxxxxxxxxxxx>
- Date: Sat, 10 Oct 2009 10:58:26 -0500
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
Other related posts:
