in programming you proceed even with 13 because the program does not know that 13 is prime. It will try to go one step further and in that moment it will see that it is not posible. so the program will do sqrt(13)=3 and it will try to factorise 13 with 2 and 3 and it will see that none of these is a prime factor of 13 so 13 is prime. I've given a code in a previous message, but it seems that alex didn't see it.
----- Original Message ----- From: "qubit" <lauraeaves@xxxxxxxxx>
To: <programmingblind@xxxxxxxxxxxxx> Sent: Sunday, October 11, 2009 2:23 AM Subject: Re: prime factors shortcut question
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 failsso 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 notquite 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 questionrandom? 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 questionno, 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 questionI will try it. A question, though: is this only for certain numbers? Lookat 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 questiontake 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 notreturn 0. What do I do? Do I get the floor or ceiling of the square rootoperation? 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
__________View the list's information and change your settings at //www.freelists.org/list/programmingblind
