Re: prime factors shortcut question
- From: Varun Khosla <varun.lists@xxxxxxxxx>
- To: programmingblind@xxxxxxxxxxxxx
- Date: Sat, 10 Oct 2009 23:10:12 -0700
oopse!
How could I miss that, anyway, yes,u r right. It worked that way.
On 10/10/09, black ares <matematicianu2003@xxxxxxxxxxx> wrote:
> wrong.
> for will execute one time because i<=sq means
> while i<=sq do
> so i=3 sq=3 so for enters.
> next time when i will be 5
> for will be skyped.
>
> ----- Original Message -----
> From: "Varun Khosla" <varun.lists@xxxxxxxxx>
> To: <programmingblind@xxxxxxxxxxxxx>
> Sent: Saturday, October 10, 2009 5:01 PM
> Subject: Re: prime factors shortcut question
>
>
>> 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
>>
>
> __________
> 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:
