• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Finding all factors from the list of prime factors.

 
Ranch Hand
Posts: 537
Eclipse IDE Python Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Well, this is kind of confusing me to find out all factors of a number using the list of primes. The primes can be combined is all possible combination to get the other factors of the number. But, some of the factors are missing it numbers which are high like 4095 and more. My code for getting prime factors is


and combining the primes is


Please help me in getting all factors of a number from the primes. Thanks in advance
 
Marshal
Posts: 79151
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
If you have a List of primes, you might do well to serialise it for future reference; why calculate the primes anew every time?
How about using a sieve of Eratosthenes, then populating your list of primes, then you can iterate through the List of numbers, and for an example like 4095 (3 × 3 × 5 × 7 × 13) you can calculate the factors very easily.
Use a pencil and paper and work out the prime factors of such a number: go through the method on paper then write down exactly how you did it. Then you have some pseudocode and you can easily convert that to real code. I think you are correctly checking for prime factors. How did you validate your isPrime() method? What you have written, with 8 unidentifiable local variables, looks very complicated.
 
Nitish Bangera
Ranch Hand
Posts: 537
Eclipse IDE Python Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Well isPrime is easy. check the number divisibility with i = 0 to i < squareroot of the number. Well that is understood. Well what i have wrritten is a kind of pseudocode only. l1 is a set whereas l has the primes. The method i thought is

eg:- 4095 = 3^2 * 5^1 *7^1 * 13^1. So 3^0 5^0 7^0 13^0, then 3^0 5^1 7^1 13^1 the 3^1 5^0 7^0 13^0 and so on for every number 5(0,1),7(0,1) and 13(0,1).

On paper every possible combination is calculated. But to convert it to an implementation is kind of giving me a problem.
 
Campbell Ritchie
Marshal
Posts: 79151
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
You implement what you would do on paper. I have already said you appear to be checking whether a number divides by something. But your prime numbers method is still incomprehensible. You appear to be confusing sets an lists; the two are very different.

I still think using a sieve of Eratosthenes to create a set of prime numbers which can be reused is a better approach.
reply
    Bookmark Topic Watch Topic
  • New Topic