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

• (3 Pages)
• 1
• 2
• 3

## 36 Replies - 12251 Views - Last Post: 01 July 2011 - 07:56 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=237814&amp;s=470b19d0f1253874933f0d479789df4a&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 zafarj

Reputation: -7
• 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

◦ 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.

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

• Games, Graphs, and Auctions

Reputation: 12243
• Posts: 45,332
• 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.

### #3 zafarj

Reputation: -7
• 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;

while (i <= number) {

int i1 = (int) Math.ceil(Math.sqrt(i));

while (i1 > 1) {

if ((i != i1) && (i % i1 == 0)) {

}

i1--;
}

System.out.println(i);
}
}

System.out.println("Nr of prime numbers found: " + primeNumberCounter);
}

```

### #4 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12243
• Posts: 45,332
• 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.

### #5 Mila

Reputation: 34
• 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

macosxnerd101, 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?

### #6 Karel-Lodewijk

Reputation: 454
• 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 ?

### #7 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12243
• Posts: 45,332
• 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

Mila, on 01 July 2011 - 01:01 PM, said:

macosxnerd101, 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.

### #8 jon.kiparsky

• Beginner

Reputation: 10985
• Posts: 18,746
• 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.

### #9 zafarj

Reputation: -7
• 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

macosxnerd101, 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.

### #10 pbl

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

Reputation: 8378
• 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 ?

### #11 jon.kiparsky

• Beginner

Reputation: 10985
• Posts: 18,746
• 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.

### #12 zafarj

Reputation: -7
• 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

pbl, 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.

### #13 jon.kiparsky

• Beginner

Reputation: 10985
• Posts: 18,746
• 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?

### #14 zafarj

Reputation: -7
• 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

jon.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

jon.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?

### #15 jon.kiparsky

• Beginner

Reputation: 10985
• Posts: 18,746
• 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