Alladaskill17 Posted March 2, 2009 Share Posted March 2, 2009 (edited) If Someone types in a number, um.. example of 60. How could I show all of the smallest factors that go into it. Such as: 60 = 2*2*3*5. I would appreciate some help with the logic and code, please. Edited March 4, 2009 by Alladaskill Link to comment Share on other sites More sharing options...
0 PyX Posted March 2, 2009 Share Posted March 2, 2009 There's a function called "modulus" or "modulo" or something, that tells you the remainder of a division. i.e. 62 mod 3 = 2 You have to create a while loop that verifies if the number is dividible (woah, is this a word?) by the smallest factor. If it is, it does so and it adds this number into an array. You may have to resize your array up before adding your number. If it is not, it looks for another premier factor (either you have a premade list, or you have a smart code that looks for numbers itself) That reminds me of one of my homeworks I had to do last semester in Visual Basic. :) Very straightforward. Link to comment Share on other sites More sharing options...
0 ViZioN Posted March 2, 2009 Share Posted March 2, 2009 I think what you're looking for is prime factors. I'm sure there's plenty code online you can use although as I'm guessing this is a homework exercise you shouldn't be. Link to comment Share on other sites More sharing options...
0 eccofresh Posted March 2, 2009 Share Posted March 2, 2009 I'd count from 1 to the number, in your case 60, with a for next loop and then check with modulo if you number can be devided by the counted number. if yes, store the current number of your loop in an array or so Link to comment Share on other sites More sharing options...
0 Andre S. Veteran Posted March 3, 2009 Veteran Share Posted March 3, 2009 The naive algorithm is to check if n%a = 0, for each a between 2 and sqrt(n). Each a that satisfies the condition is a factor. Link to comment Share on other sites More sharing options...
0 +Xinok Subscriber² Posted March 3, 2009 Subscriber² Share Posted March 3, 2009 An example in Python. If you don't know Python, the code should still be easy enough to interpret. input = 60 primes = [] mod = 2 while input >= mod*mod: if input % mod == 0: primes += [mod] input /= mod else: mod += 1 primes += [input] Link to comment Share on other sites More sharing options...
0 Andre S. Veteran Posted March 3, 2009 Veteran Share Posted March 3, 2009 I'd count from 1 to the number, in your case 60, with a for next loop and then check with modulo if you number can be devided by the counted number. if yes, store the current number of your loop in an array or soThat is incorrect for three reasons :1 is not a prime, hence not a prime factor of any number Not all numbers that divide n are primes Trying modulo on all numbers up to n might lead to too many prime factors. Let's try your algorithm with 60 : 60 % 1 == 0 -> [1] // Incorrect - 1 is not a prime 60 % 2 == 0 -> [1, 2] 60 % 3 == 0 -> [1, 2, 3] 60 % 4 == 0 -> [1, 2, 3, 4] // Incorrect - 4 is not a prime 60 % 5 == 0 -> [1, 2, 3, 4, 5] 60 % 6 == 0 -> [1, 2, 3, 4, 5, 6] // Incorrect - 6 is not a prime 60 % 7 != 0 60 % 8 != 0 60 % 9 != 0 60 % 10 == 0 -> [1, 2, 3, 4, 5, 6, 10] // Incorrect - 10 is not a prime 60 % 11 != 0 60 % 12 == 0 -> [1, 2, 3, 4, 5, 6, 10, 12] // Incorrect - 12 is not a prime 60 % 13 != 0 60 % 14 != 0 60 % 15 == 0 -> [1, 2, 3, 4, 5, 6, 10, 12, 15] // Incorrect - 15 is not a prime At this point, even if we find a new prime that divides 60, it is superfluous; the prime factors of 60 are 2, 3, and 5, no need for more. So what the algorithm really needs to do is set : list of prime factors n : number to factorize for a = integers between 2 and sqrt(n) if a is prime if a divides n add a to set My previous reply was incorrect as well, I apologize. Link to comment Share on other sites More sharing options...
0 Alladaskill17 Posted March 4, 2009 Author Share Posted March 4, 2009 So how would I code this? I am currently lost & still learning with the book and my ( very useless ) professor. Link to comment Share on other sites More sharing options...
0 Alladaskill17 Posted March 4, 2009 Author Share Posted March 4, 2009 BUMP Link to comment Share on other sites More sharing options...
0 +Xinok Subscriber² Posted March 4, 2009 Subscriber² Share Posted March 4, 2009 input = 60 primes = [] mod = 2 while input >= mod*mod: while input % mod == 0: primes += [mod] input /= mod mod += 1 primes += [input] My code works, I've tested it. I just changed the if statement to a while loop. 2 is the first prime, so initialize mod to 2. If input is divisible by mod (input % mod == 0), then add mod to the list of factors, and divide input by mod (input /=mod). Repeat this step until input is no longer divisible by mod. Increment mod by 1. Repeat while input >= mod*mod Last step, there's still one factor missing from the list, and that's input. So add input to the list of factors. This is how it works out: 60/2 30/2 15/3 5 2*2*3*5 = 60 Link to comment Share on other sites More sharing options...
0 Alladaskill17 Posted March 4, 2009 Author Share Posted March 4, 2009 Java equivalent? Link to comment Share on other sites More sharing options...
0 Alladaskill17 Posted March 4, 2009 Author Share Posted March 4, 2009 BUMP + A smallest factor x of y is defined as a prime number (greater than 1) that divides y. For example, all the smallest factors of 60 are 2, 2, 3, and 5; all the smallest factors of 11 is 11; all the smallest factors of 984 are 2, 2, 2, 3, and 41. Still requesting help. Link to comment Share on other sites More sharing options...
0 ViZioN Posted March 4, 2009 Share Posted March 4, 2009 You've already been given an algorithm to solve the problem. How about showing us the code you've done already and where you're stuck? Link to comment Share on other sites More sharing options...
0 tunafish Posted March 4, 2009 Share Posted March 4, 2009 How about you stop being so impatient with all the bumps etc. Why dont you jsut go ask your prof for help rather than trying to get other people on neowin doing all the coding for your college work so you can reap the rewards. Hell ever better read the book! When i was at college no professor would set any type of assignment or homework on code that was not covered in a lesson. The member here have given you ENOUGH information for you to figure this out, dam school kids so lazy. Atleast make an effort instead of basically asking member to do the work So far you have not even produced ANY code, not even basic Pseudo-code. Link to comment Share on other sites More sharing options...
0 PyX Posted March 5, 2009 Share Posted March 5, 2009 Yeah seriously, you shouldn't need help at all to code this if you're in a class. My answer should have helped you A LOT already. If you're doing it on your own (which I hope not - because it's useless), then fine, you're learning by trial and error. But since you must be in a class, go ask your classmates or the teacher himself. When you'll be in your exams, you'll be glad of the work you did in your homework, trust me. The only people I know who totally choked on this class were people who didn't do the homework, no kidding. Link to comment Share on other sites More sharing options...
Question
Alladaskill17
If Someone types in a number, um.. example of 60.
How could I show all of the smallest factors that go into it. Such as:
60 = 2*2*3*5.
I would appreciate some help with the logic and code, please.
Edited by AlladaskillLink to comment
Share on other sites
14 answers to this question
Recommended Posts