Re: prime factors shortcut question
- From: Varun Khosla <varun.lists@xxxxxxxxx>
- To: programmingblind@xxxxxxxxxxxxx
- Date: Sat, 10 Oct 2009 07:01:53 -0700
Hi,
If I'm not wrong, the code you mentioned seems to be falling into an
infinite loop?
Taking the number 22 as you did,
the first while loop cycle completes with num=3 as the following if
condition holds true
if(num%2==0) // 22mod2 = 0
But during the second cycle, this condition doesn't hold (which is
ok), but the proceeding for loop doesn't execute, as sq and i will be
equivalent (3):
for(i=3; i<=sq; i+=2) // i = sq, condition holds, loop doesn't enter
into first cycle.
and since i and sq are equal, following condition doesn't also hold:
if(i>sq)
{
ready=true;
.... infinity
I think, the above condition can be made as:
if (i >= sq)
just a suggestion
Regards,
Varun
On 10/9/09, black ares <matematicianu2003@xxxxxxxxxxx> wrote:
> in fact you take the number 22
> you will take the square root it is 4.
> you search amoung all primes less than square root until you find one which
> divides your number.
> In our case you find 2.
> You divide your number by that prime found and for the result you repeat the
> algorithm
> You repeat this algorithm until you will not find any prime less than the
> square root which divides your number.
> In our case 22/2=11 square root of 11 is 3 the only prime less than 3 is 2
> you take the modulo of 11 to 2 and you find that is 1 not 0 so stop.
> Now the last number you found is also a prime factor so the result of your
> program is 2, 11.
> In a pseudo language I see tthe code like this:
>
> int num=22;//any other number works
> bool ready=false;
> arraylist results=new arraylist();
> while(!ready)
> {
> if(num%2==0)
> {
> results.add(2);
> num/=2;
> continue;
> }
> int sq=Math.Floor(Math.Sqrt(num));
> int i=3;
> for(i=3; i<=sq; i+=2)
> {
> if(num%i==0)
> {
> num/=i;
> results.add(i);
> break;
> }
>
> }
> if(i>sq)
> {
> ready=true;
> results.add(num);
> }
> }
>
> ----- Original Message -----
> From: "qubit" <lauraeaves@xxxxxxxxx>
> To: <programmingblind@xxxxxxxxxxxxx>
> Sent: Saturday, October 10, 2009 7: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
>
>
--
Varun
__________
View the list's information and change your settings at
//www.freelists.org/list/programmingblind
Other related posts:
