# Finding Prime Numbers.

Page 1 of 1

## 8 Replies - 748 Views - Last Post: 29 January 2014 - 12:52 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=339151&amp;s=a4219573f8e7cd37c01da3f0e447c45d&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 shamieh

Reputation: -4
• Posts: 146
• Joined: 14-September 13

# Finding Prime Numbers.

Posted 28 January 2014 - 11:04 PM

I'm trying to output an algorithm that will let the user enter a number, I will then take that number and find all the factors of that number. Then, I will Display back to the User ALL of the PRIME NUMBERS (When I say prime numbers I mean any number that can be sqrtd back to its original number... like 4, 9, 36 (bc 2*2 = 4, 3 * 3 = 9 etc,] And those are all factors of 36, (including 36 which is 6 *6) So I have 95% of the code But I can't figure out how I'm going to COUNT the Prime numbers. The problem I'm having is the algorithm is saying "Hey is this a prime number? Yea!" But then while it Checks to see if it is a prime number it actually stores the result giving me 0. I want to display back to the user all of the prime numbers from the Integer they entered. For exampel if they enter 36, I want to display the message, your prime factors are: 4, 9, 36

Check out my code

```#include <iostream>
#include <iomanip>

using namespace std;

//ALGORITHM TO FIND ALL THE FACTORS OF A #

int main()
{

int num_1;
int i;
int counter = 0;

cout<<"Enter Number to be factored:";

cin>> num_1;

for(i = 2; i <= num_1; i++)
{
if(num_1 % i == 0)
{
cout << "-----FACTORS OF YOUR #-------" << endl;
cout << setw(5) << i;
counter ++; //INCREASE COUNTER EVERY TIME LOOP EXECUTES
bool prime = true;
for (i = 2; i < num_1; ++i)
{
if (num % i == 0)
{
//HERE I WANT TO SAY THE PRIME NUMBERS OF YOUR INPUT ARE:  AND HAVE THEM LISTED.

}
}

if(counter == 4)
{
cout << endl; //IF COUNTER EQUALS 4 OUTPUT END LINE
counter = 0; //RESET COUNTER TO 0 AFTER COUNTER REACHES 4
}
}
}
}

```

Is This A Good Question/Topic? 0

## Replies To: Finding Prime Numbers.

### #2 Ntwiles

Reputation: 148
• Posts: 831
• Joined: 26-May 10

## Re: Finding Prime Numbers.

Posted 28 January 2014 - 11:32 PM

You're saying you want to output the found prime numbers from inside your for loop. You can do that, but you'll have to output them line by line as you find them. If you want to output them all at once,you should add them to an array and output that AFTER the nested for loop iterations have finished.

• جوروترا

Reputation: 284
• Posts: 980
• Joined: 18-April 09

## Re: Finding Prime Numbers.

Posted 29 January 2014 - 02:37 AM

Quote

A Prime Number can be divided evenly only by 1 or itself.
And it must be a whole number greater than 1.

Here is how to print the 100 first prime numbers:

http://stackoverflow...m-1-through-100

### #4 Skydiver

• Code herder

Reputation: 5104
• Posts: 16,884
• Joined: 05-May 12

## Re: Finding Prime Numbers.

Posted 29 January 2014 - 09:30 AM

Ntwiles, on 29 January 2014 - 01:32 AM, said:

You're saying you want to output the found prime numbers from inside your for loop. You can do that, but you'll have to output them line by line as you find them. If you want to output them all at once,you should add them to an array and output that AFTER the nested for loop iterations have finished.

Not quite true... If the OP is very careful with his/her output, they can print a number without a carriage return following the number. Only when the loop is over will the print out the carriage return. This gives the effect of printing all the prime numbers on a single line.

### #5 Ntwiles

Reputation: 148
• Posts: 831
• Joined: 26-May 10

## Re: Finding Prime Numbers.

Posted 29 January 2014 - 11:45 AM

tarmizi_adam2005, on 29 January 2014 - 04:37 AM, said:

Quote

A Prime Number can be divided evenly only by 1 or itself.
And it must be a whole number greater than 1.

Here is how to print the 100 first prime numbers:

http://stackoverflow...m-1-through-100

I meant C line by line, not console line by line, but good point anyway.

This post has been edited by Ntwiles: 29 January 2014 - 11:45 AM

### #6 Skydiver

• Code herder

Reputation: 5104
• Posts: 16,884
• Joined: 05-May 12

## Re: Finding Prime Numbers.

Posted 29 January 2014 - 12:07 PM

shamieh, on 29 January 2014 - 01:04 AM, said:

I'm trying to output an algorithm that will let the user enter a number, I will then take that number and find all the factors of that number. Then, I will Display back to the User ALL of the PRIME NUMBERS (When I say prime numbers I mean any number that can be sqrtd back to its original number... like 4, 9, 36 (bc 2*2 = 4, 3 * 3 = 9 etc,] And those are all factors of 36, (including 36 which is 6 *6). ... I want to display back to the user all of the prime numbers from the Integer they entered. For exampel if they enter 36, I want to display the message, your prime factors are: 4, 9, 36

I think you are in serious trouble if that is your expected output. The numbers 4, 9, and 36 are not prime.

Did you mean "perfect squares"?

### #7 shamieh

Reputation: -4
• Posts: 146
• Joined: 14-September 13

## Re: Finding Prime Numbers.

Posted 29 January 2014 - 12:18 PM

Skydiver, on 29 January 2014 - 07:07 PM, said:

shamieh, on 29 January 2014 - 01:04 AM, said:

I want to display back to the user all of the prime numbers from the Integer they entered. For exampel if they enter 36, I want to display the message, your prime factors are: 4, 9, 36

I think you are in serious trouble if that is your expected output. The numbers 4, 9, and 36 are not prime.

I didn't explain well enough. What I am trying to do is this:

1) Hey user give me an integer between 2 & 5000!
*User types in 36 *
2)Ok user, now I'm going to find all of the FACTORS of 36
*algorithm finds all of the FACTORS of 36.. i.e. (4 * 9) (6 * 6 ) (18 *2) ...etc etc (1,2,3,4,6,9,12,18,36)
3)Ok user, now I'm going to display to you all of the FACTORS of your NUMBER that are "PERFECT SQUARES" .
*Algorithm to find all of the numbers that can be sqrt* (i.e. finds 4, 9, 36 BECAUSE 2 * 2 = 4, 3 * 3 = 9 & 6 * 6 = 36
4)Ok user, here are the numbers that are perfect squares AND are factors of the number you inputted: 4, 9, 36.

See what I'm saying?

I know how to find the factors of the number, that algorithm is easy. The problem is I don't know how to count the SQUARE FREE numbers that are also FACTORS of that number.

This post has been edited by shamieh: 29 January 2014 - 12:19 PM

### #8 shamieh

Reputation: -4
• Posts: 146
• Joined: 14-September 13

## Re: Finding Prime Numbers.

Posted 29 January 2014 - 12:36 PM

For example, all I've got working right now is how to find the factors of the integer entered by the user..What can I put to count the perfect squares?

```#include <iostream>
#include <iomanip>

using namespace std;

int main(){

int num;

cout << "YOUR #: "; cin >> num;

for (int i = 1; i <= num; ++i )
{
if ( num % i == 0 )
{
cout << i << " ";
}
}

}
```

### #9 Skydiver

• Code herder

Reputation: 5104
• Posts: 16,884
• Joined: 05-May 12

## Re: Finding Prime Numbers.

Posted 29 January 2014 - 12:52 PM

First find all the factors, put them in an array or a list.
Next iterate over the array or list, and call sqrt() on each of the items. If the result has a fractional part, then it's not a perfect square. If it does not have a fractional part, then it' a perfect square, store it in another array or list.
That last array or list will give you both the factors that are perfect squares.

(Some shortcuts can be taken by skipping the intermediate array or list.)

The weird part is that that you say all you want is a count of the perfect square factors, but in your descriptions you say you want to output the perfect square factors. Which is which?