to find the prime factors of a number and then print them all in a str

  • (3 Pages)
  • +
  • 1
  • 2
  • 3

36 Replies - 11556 Views - Last Post: 01 July 2011 - 07:56 PM Rate Topic: -----

#1 zafarj  Icon User is offline

  • D.I.C Head

Reputation: -7
  • View blog
  • Posts: 79
  • Joined: 01-July 11

to find the prime factors of a number and then print them all in a str

Posted 01 July 2011 - 09:19 AM

public static String findPrimeNumbers(int number)
◦ Finds all the prime numbers less than or equal to number
◦ You will need to use nested loops. The outer loop will go through all the possible numbers you are
testing for prime. The inner loop will be used to test the current outer loop value to see if it is prime.

I am not able to figure out the inner loop.
Please someone help me

This post has been edited by macosxnerd101: 01 July 2011 - 09:22 AM
Reason for edit:: Title renamed to be more descriptive

Is This A Good Question/Topic? 0
  • +

Replies To: to find the prime factors of a number and then print them all in a str

#2 macosxnerd101  Icon User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12148
  • View blog
  • Posts: 45,161
  • Joined: 27-December 08

Re: to find the prime factors of a number and then print them all in a str

Posted 01 July 2011 - 09:20 AM

Check out the Sieve of Eratosthenes. This is the algorithm being described. Try to implement it and we will be happy to help you with your good faith efforts. :)
Was This Post Helpful? 1
  • +
  • -

#3 zafarj  Icon User is offline

  • D.I.C Head

Reputation: -7
  • View blog
  • Posts: 79
  • Joined: 01-July 11

Re: to find the prime factors of a number and then print them all in a str

Posted 01 July 2011 - 09:53 AM

can you see my coding i am having some problems
 public static String findPrimeNumbers(int number)
  { 
    int i = 2;
    int primeNumberCounter = 0;
    
    while (i <= number) {
      
      int i1 = (int) Math.ceil(Math.sqrt(i));
      
      boolean isPrimeNumber = false;
      
      while (i1 > 1) {
        
        if ((i != i1) && (i % i1 == 0)) {
          isPrimeNumber = false;
         
        } else if (!isPrimeNumber) {
          isPrimeNumber = true;
        }
        
        i1--;
      }
      
      if (isPrimeNumber) {
        System.out.println(i);
        ++primeNumberCounter;
      }
    }
    
    System.out.println("Nr of prime numbers found: " + primeNumberCounter);
  }


Was This Post Helpful? 0
  • +
  • -

#4 macosxnerd101  Icon User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12148
  • View blog
  • Posts: 45,161
  • Joined: 27-December 08

Re: to find the prime factors of a number and then print them all in a str

Posted 01 July 2011 - 09:55 AM

The first thing I would suggest is using a List<Integer> to generate all the numbers from 2-n, save any number where x%2 == 0 and x != 2. In other words, all numbers from 2-n, except even numbers > 2. Then prune as described in the algorithm.
Was This Post Helpful? 0
  • +
  • -

#5 Mila  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 34
  • View blog
  • Posts: 193
  • Joined: 28-October 06

Re: to find the prime factors of a number and then print them all in a str

Posted 01 July 2011 - 10:01 AM

View Postmacosxnerd101, on 01 July 2011 - 10:55 AM, said:

save any number where x%2 == 0 and x != 2


Don't you mean x%2!=0?
Was This Post Helpful? 0
  • +
  • -

#6 Karel-Lodewijk  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 454
  • View blog
  • Posts: 864
  • Joined: 17-March 11

Re: to find the prime factors of a number and then print them all in a str

Posted 01 July 2011 - 10:01 AM

naive approach, test all numbers between 1 and the number you are testing to see if you devide the number if the remainder is 0.

Spoiler


Now start thinking, do I need to check every number ?
Was This Post Helpful? 1
  • +
  • -

#7 macosxnerd101  Icon User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12148
  • View blog
  • Posts: 45,161
  • Joined: 27-December 08

Re: to find the prime factors of a number and then print them all in a str

Posted 01 July 2011 - 11:17 AM

View PostMila, on 01 July 2011 - 01:01 PM, said:

View Postmacosxnerd101, on 01 July 2011 - 10:55 AM, said:

save any number where x%2 == 0 and x != 2


Don't you mean x%2!=0?

In this case, save is being used to mean except, or excluding.
Was This Post Helpful? 0
  • +
  • -

#8 jon.kiparsky  Icon User is online

  • Chinga la migra
  • member icon


Reputation: 10682
  • View blog
  • Posts: 18,296
  • Joined: 19-March 11

Re: to find the prime factors of a number and then print them all in a str

Posted 01 July 2011 - 12:42 PM

naive approach, test all numbers between 1 and the number you are testing to see if you devide the number if the remainder is 0.


Yes, that's a good way to start. Thinking about which numbers don't need to be tested is handy. For example, consider that three is a factor of 9. If you've already found that three is not a factor of the number in question, then you know that 9 isn't a factor, don't you?

Then there's the upper bound: do you need to examine every number up to n, or is there a smaller value? To explore this, try to find a value around which all of the factors of a number show symmetry - a number which marks the "multiplicative midpoint" of n. For addition, as an example, the midpoint is n/2: for any number less than n/2, there is exactly one number greater than n/2 which can be added to it to make n. There is a midpoint for multiplication as well, and it's fun to try to figure out where it is - once you find it, try to prove to yourself that it is the midpoint. This isn't a difficult exercise, but it requires a certain "aha" moment.
Was This Post Helpful? 0
  • +
  • -

#9 zafarj  Icon User is offline

  • D.I.C Head

Reputation: -7
  • View blog
  • Posts: 79
  • Joined: 01-July 11

Re: to find the prime factors of a number and then print them all in a str

Posted 01 July 2011 - 02:06 PM

View Postmacosxnerd101, on 01 July 2011 - 09:55 AM, said:

The first thing I would suggest is using a List<Integer> to generate all the numbers from 2-n, save any number where x%2 == 0 and x != 2. In other words, all numbers from 2-n, except even numbers > 2. Then prune as described in the algorithm.


I haven't learn List<Integer> in the class yet. So I don't what it is and I cant really use it.
Was This Post Helpful? 0
  • +
  • -

#10 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8378
  • View blog
  • Posts: 31,956
  • Joined: 06-March 08

Re: to find the prime factors of a number and then print them all in a str

Posted 01 July 2011 - 02:11 PM

Can you at least use an array ?
Was This Post Helpful? 0
  • +
  • -

#11 jon.kiparsky  Icon User is online

  • Chinga la migra
  • member icon


Reputation: 10682
  • View blog
  • Posts: 18,296
  • Joined: 19-March 11

Re: to find the prime factors of a number and then print them all in a str

Posted 01 July 2011 - 02:11 PM

Don't worry about the List part for the moment. Think about what you're tying to do, not what tools you're going to use to do it. If you actually need a List, it'll be easier to figure out how to use it once you know what you want to use it for.
Was This Post Helpful? 0
  • +
  • -

#12 zafarj  Icon User is offline

  • D.I.C Head

Reputation: -7
  • View blog
  • Posts: 79
  • Joined: 01-July 11

Re: to find the prime factors of a number and then print them all in a str

Posted 01 July 2011 - 02:14 PM

View Postpbl, on 01 July 2011 - 02:11 PM, said:

Can you at least use an array ?


No I cant because I have just started arrays in the class jut yesterday.
Was This Post Helpful? 0
  • +
  • -

#13 jon.kiparsky  Icon User is online

  • Chinga la migra
  • member icon


Reputation: 10682
  • View blog
  • Posts: 18,296
  • Joined: 19-March 11

Re: to find the prime factors of a number and then print them all in a str

Posted 01 July 2011 - 02:18 PM

Okay, then let's put aside the Sieve approach for the moment. Neither arrays or lists are needed, they just make one approach possible. Again: think about the problem, and how you want to solve it.

What are the particular problems you mentioned in your original post? You simply say you can't figure out the inner loop. What is it that you want to do, and what can't you figure out?
Was This Post Helpful? 0
  • +
  • -

#14 zafarj  Icon User is offline

  • D.I.C Head

Reputation: -7
  • View blog
  • Posts: 79
  • Joined: 01-July 11

Re: to find the prime factors of a number and then print them all in a str

Posted 01 July 2011 - 02:24 PM

View Postjon.kiparsky, on 01 July 2011 - 12:42 PM, said:

naive approach, test all numbers between 1 and the number you are testing to see if you devide the number if the remainder is 0.


Yes, that's a good way to start. Thinking about which numbers don't need to be tested is handy. For example, consider that three is a factor of 9. If you've already found that three is not a factor of the number in question, then you know that 9 isn't a factor, don't you?

Then there's the upper bound: do you need to examine every number up to n, or is there a smaller value? To explore this, try to find a value around which all of the factors of a number show symmetry - a number which marks the "multiplicative midpoint" of n. For addition, as an example, the midpoint is n/2: for any number less than n/2, there is exactly one number greater than n/2 which can be added to it to make n. There is a midpoint for multiplication as well, and it's fun to try to figure out where it is - once you find it, try to prove to yourself that it is the midpoint. This isn't a difficult exercise, but it requires a certain "aha" moment.


Well, since you are asking for which number so basically i need to take number from other method which is input by the user

View Postjon.kiparsky, on 01 July 2011 - 02:18 PM, said:

Okay, then let's put aside the Sieve approach for the moment. Neither arrays or lists are needed, they just make one approach possible. Again: think about the problem, and how you want to solve it.

What are the particular problems you mentioned in your original post? You simply say you can't figure out the inner loop. What is it that you want to do, and what can't you figure out?


How should check that starting from 2 till the number less than or equal to it all the prime numbers occuring?
Was This Post Helpful? 0
  • +
  • -

#15 jon.kiparsky  Icon User is online

  • Chinga la migra
  • member icon


Reputation: 10682
  • View blog
  • Posts: 18,296
  • Joined: 19-March 11

Re: to find the prime factors of a number and then print them all in a str

Posted 01 July 2011 - 02:27 PM

Quote

Well, since you are asking for which number so basically i need to take number from other method which is input by the user


Okay, you're getting the number to test from the user. But when you have a number to test - let's call it n - how do you test it? The naive approach is to simply step through all of the positive integers less than n and check each for divisibility - it looks like that's pretty much what you're doing there. What I'm talking about in the bit you quoted is making that process a little more efficient.

Let's get the naive version working before we fix it, okay? What are the problems you're having with the code that you posted? What does it do that it shouldn't, or what doesn't it do that it should be doing?

EDIT:

Quote

How should check that starting from 2 till the number less than or equal to it all the prime numbers occuring?


You mean you want to make a list of the prime numbers from 2 to n?
Okay. So you'll make a loop from 2 to n, and check each number to see if it's prime. If it is, you'll print it to the screen, if not, you'll move on.
So, for any given number, how can you tell if it's prime?

This post has been edited by jon.kiparsky: 01 July 2011 - 02:30 PM

Was This Post Helpful? 0
  • +
  • -

  • (3 Pages)
  • +
  • 1
  • 2
  • 3