Getting Prime Factors of first 1000 numbers

Pages: 12
I need to write a few C++ program as a practice problem for my book that I'm learning out of (Jumping into C++). Right now I want to focus on three of them, the first of which is one where I have to find the prime factors of the first 1000 numbers and then find and the print the ones that sum up to prime numbers.

The book at already has a complete program on how to find and print the prime numbers out of the first 100 numbers. So I just have to build off of that, I guess, the problem is that I don't know how to find prime factorizations in C++.

These are the three Practice Problems I mentioned:

1. Implement the source code that turns numbers into English text.
2. Think about how you would go in the opposite direction, reading English text and translating it
into source code. Is this easier or harder than the earlier algorithm? How would you handle bad
input?
3. Design a program that finds all numbers from 1 to 1000 whose prime factors, when added
together, sum up to a prime number (for example, 12 has prime factors of 2, 2, and 3, which
sum to 7, which is prime). Implement the code for that algorithm.

Another issue I'm currently having is actually with this Practice Problem:

Write a program that provides the option of tallying up the results of a poll with 3 possible
values. The first input to the program is the poll question; the next three inputs are the possible
answers. The first answer is indicated by 1, the second by 2, the third by 3. The answers are
tallied until a 0 is entered. The program should then show the results of the poll—try making a
bar graph that shows the results properly scaled to fit on your screen no matter how many
results were entered.

This is the code I've got so far:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>

using namespace std;

int user_chosen_option(int user_input);

int main()
{
int user_input;

cout << "What is your favorite type of music?";
cout << "Option 1: Rock\n";
cout << "Option 2: Metal\n";
cout << "Option 3: Jazz\n";
cin >> user_input;
user_chosen_option(user_input);
}

int user_chosen_option(int user_input)
{
switch(user_input)
{
case 1:
cout << "That's an interesting choice in music.  "
}
}


And as for the program for the prime number generator for the first 100 numbers, here is the code: #include <iostream>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <math.h>

// note the use of function prototypes

bool isDivisible (int number, int divisor);

bool isPrime (int number);

using namespace std;

int main ()
{
    for ( int i = 0; i < 100; i++ )
    {

        if ( isPrime( i ) )
        {
            cout << i << endl;
        }
    }
}

bool isPrime (int number)
{
    for (int i = sqrt((double)number); i < number; i++)
        {
            if ( isDivisible( number, i ) )
            {
                return false;
            }
        }
        return true;
}
bool isDivisible (int number, int divisor)
{
    return number % divisor == 0;
}


The book said that using 2 as the number to start with wouldn't be efficient enough and suggested using the square-root of the number currently being checked. That's why I did "for (int i = sqrt((double)num); . . . ) for the initialization part of that for-loop. The original sample code in the book uses "for (int i = 2; . . . ) for the initialization.
Last edited on
I'll only answer to the Prime problem you are facing, but first of, doesn't it allready work?
Either way I don't understand why the book suggests using sqrt, it works fine here.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>

bool isDivisible (int number, int divisor)
{
	return number % divisor == 0;
}
bool isPrime1 (int number)
{
	if(number < 2) // 1 and 0 are no primes
		return false;

	for (int i = 2; i <= number / 2; ++i) // no need to go further than number/2
	{
		if ( isDivisible( number, i ) )
		{
			return false;
		}
	}
	return true;
}
bool isPrime2 (int number) // both work
{
	int count = 0;

	for (int i = 1; i <= number; ++i)
	{
		if ( isDivisible( number, i ) )
		{
			count++;
		}
	}
	return count==2; // exactly 2 different divisors
}

int main()
{
	for(int i = 0; i < 1000; ++i)
	{
		std::cout << i << " is ";
		if(!isPrime(i))
			std::cout << " not ";
		std::cout << "a prime" << std::endl;
	}

	return 0;
}

output: 
0 is  not a prime
1 is  not a prime
2 is a prime
3 is a prime
4 is  not a prime
5 is a prime
6 is  not a prime
7 is a prime
8 is  not a prime
9 is  not a prime
10 is  not a prime
11 is a prime
12 is  not a prime
13 is a prime
...
What I wanted to ask for was help figuring out a working algorithm for a program that printed the prime factors of the first 1000 numbers that, when added up, gave us prime numbers. The code I have now only gives me prime numbers out of the first 100 numbers, the for-loop of which I could easily change to iterate over the first 1000 numbers.

Here is the pseudocode I'm thinking of so far:
1
2
3
4
5
6
7
8
9
// for every 1000 of the first bunch of numbers, check if the number is prime
// if (number isPrime())
// use expression <number_being_checked % number_being_compared_against == 0;>

// if (number_being_checked % number_being_compared_against == 0)
// for every number found from dividing the two numbers, check if number is prime
// add up prime numbers and check if the sums are prime

// else, return false in bool function isPrimeFactor() (if I write such a function) 


If this is alright, which I want to discuss here, I'll try to turn into code and see if it runs the way I want it to.

I might need helping find the right way to implement it, though.
Last edited on
ah okey, i get it now

So basically you want to add all prime factors and see if the result is a prime number itself?
The sortest possible division is allways a prime.
That being said, do something like with isPrime() but add the things up and if a primeFactor is found decrease i by 1 because a primeFactor may occure more than once.

SPOILER: solution below, if you want to do it yourself don't look down

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

bool isDivisible (int number, int divisor)
{
    return number % divisor == 0;
}
bool isPrime (int number)
{
    int count = 0;

    for (int i = 1; i <= number / 2; ++i) // no need to go further than number/2
    {
        if ( isDivisible( number, i ) )
        {
            if(count++ > 2)
                break;
        }
    }
    return count==1;
}
int PrimeFactorSum (int number)
{
    int sum = 0;
    bool factorFound = false;
    
    for (int i = 2; i <= number; ++i) // number may also be a prime
    {
        if ( isDivisible( number, i ) )
        {
            if(factorFound)
                std::cout << "+"; // ugly output
            std::cout << i; // ugly output
            sum += i;                   // add the sum
            number /= i;               // decrease the number
            i--;                             // same factor may occure more than once;
            factorFound = true;
        }
    }
    if(sum==0)
        std::cout << "0";
	
    return sum;
}

int main()
{
    for(int i = 0; i < 1000; ++i)
    {
        std::cout << "prime factos of " << i << ": ";

        int sum = PrimeFactorSum(i);
        bool prime = isPrime(sum);

        std::cout << " = " << sum << ": ";
        if(!prime)
            std::cout << " not ";
        std::cout << " a Prime" << std::endl;    
    }

    return 0;
}
Last edited on
I do want it to do it myself, although I did also look at your program.

Anyway, just help me out while looking at my code.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
// Jumping into C++
// Chapter 7 Practice Problem 3
// Program to find prime factors of the first 1000 numbers
// that can be added to get prime numbers

#include <iostream>
#include <math.h>

// function prototypes

bool isDivisible (int number, int divisor);

bool isPrime (int number);

bool isFactorPrime(int number, int divisor);

using namespace std;

int main ()
{
    for (int i = 0; i < 1000; i++)
    {
        for (int j = sqrt((double)i); j < i; j++)
        {
            if (isFactorPrime(i, j))
            {
                int sum = i + j;
                if (isPrime(sum))
                {
                    cout << sum << "\n";
                }
            }
        }
    }
}

bool isPrime (int number)
{
    for (int i = sqrt((double)number); i < number; i++)
        {
            if (isDivisible(number, i))
            {
                return false;
            }
        }
        return true;
}

bool isDivisible (int number, int divisor)
{
    return number % divisor == 0;
}

bool isFactorPrime(int number, int divisor)
{
    if (number % divisor == 0)
    {
        if (isPrime(number))
        {
            return true;
        }
    }
    else
    {
        return false;
    }
    return true;
}


I like putting main() first, so I put just the prototypes of my own functions above main().

I was getting a "status 255" error and the program was crashing before because I had an uninitialized variable in main(), but now, even though the program runs, there's no output (it's completely empty and I only see that the Operating System returned 0).
Last edited on
at the beginning i is 0, therefore j is 0 too.
in isFactorPrime you do 0%0, basically a zero-division which results in an error

Also, your isPrime method does not work correctly for 0 1 2 and 3
Primes{ 2,3,5,7,11,13,17,19,} // correct output
Primes2{ 0,1,5,7,11,13,17,19,} // your isPrime output

furthermore, the if(isPrime(number)) in isFactorPrime method doesn't do anything because it returns true if number is prime and true if not.

Also, there should be no case where number%divisor==0 AND number is a prime
number%divisor==0 means that the number has a divisor
isPrime(number) means that it is only divisible through itself or 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool isFactorPrime(int number, int divisor)
{
    if (number % divisor == 0)
    {
        if (isPrime(number)) // if false, should be false everywhere
        {
            return true;
        } 
    }
    else
    {
        return false;
    }
    return true; // ... also return true
}

but I don't understand what the function should do ._.

And i don't understand the second for loop with j, what does it loop through? ._.
And why is the sum i + j?
What were your thoughts when writing this code?
Last edited on
@DragonOsman

You loop needs to start at 2 and finish at sqrt(number). Start at the sqrt root misses all the numbers before it.

Just a small thing:

Gamer2015 wrote:
Either way I don't understand why the book suggests using sqrt, it works fine here.


When doing primes, the limit should be the square root, not N/2 (which is too big). sqrt(N) is less than N/2 Think about it: if one removes all the multiples of the numbers up to sqrt(N), then all the remaining numbers up to N will be prime. When I wrote code to do primes up to 2 million, I only went to 1414 which is a lot better than 1 million. So you can see how that would impact your execution time with no gain at all.

One observation is that the book uses a naive and very inefficient method for determining primes, and is only OK for very small numbers.

If you have a look on the wiki page, there is Euler's method, which is a variation on the Sieves of Eratosthenes. Start out with a list of odd numbers then remove numbers which aren't prime. It is much more efficient to make a list of numbers that are prime using Euler's method, then do a look up on that list to see if a particular number is prime, rather than applying an algorithm to each number to see if it is prime.

Hope this helps
I think I need to write a function like "void getPrimeFactor(int number, int divisor);".

But figuring out how to find prime factors in programming is what I don't get how to do. I'll try asking my brother since he's also good at programming (older brother).

I don't want to take user input for this, I just want to print all prime factors' sums that are within the range of the first 1000 numbers.

So I just need a good algorithm that would find the prime factors of all numbers within the range of the first 1000 numbers, and then see if the prime factors of a given number add up to a prime number. And then I print all numbers that fit that description.
Last edited on
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
using namespace std;

int main () {

	int num;
	cout << "enter a number to find sum of it's prime factors: ";
	cin >> num;	
	int res=num, sum=0, i=2;
	while(i<res){
		if(res %i == 0){
			cout << "i=" << i <<" ";
			sum +=i; 			
			res /= i;
			i=1;
		}			
		i++;
	}

	if(sum==0) cout << num << " itself is a Prime Number\n";
	else{
		sum += res; cout << "res=" << res <<"\n";
		cout << "sum of prime factors of " << num << " is : " << sum << '\n';
	}	

}
Thanks for that. Could you tell me what the variable "res" stands for?

I'm thinking of taking in a user's input and checking if it's less than or equal to 1000, and I'll also say at the beginning of the program via a cout statement that the input has to be 1000 or less. Then if it's "valid" input, I'll have the program calculate its factors and print out the sum of prime factors. That'd be good, right?

About the statement: cout << "i=" << i <<" ", wouldn't it be better to say cout << "Entered number = " << i << " " or something along those lines? We don't want the user to know the name of the variable we used in the code for this, do we? lol

Edit: This is what I've got now:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
// Jumping into C++
// Chapter 7 Practice Problem 3
// Program to find prime factors of the first 1000 numbers
// that can be added to get prime numbers

#include <iostream>
#include <math.h>

// function prototypes

bool isDivisible (int number, int divisor);

bool isPrime (int number);

void factorize_and_sum(int number);

using namespace std;

int main ()
{
    int number;
    cout << "Please enter a number to find prime factors of (number must be within range of 1 - 1000): ";
    cin >> number;
    if (number <= 1000)
    {
        if (isPrime(number))
        {
            cout << "Number is already prime\n";
        }
        else if (!isPrime(number))
        {
            factorize_and_sum(number);
        }
    }
    else
    {
        cout << "Input out of range! Please a enter a number equal to or less than 1000\n";
    }
}

bool isPrime (int number)
{
    for ( int i = 2; i < number; i++)
        {
            if ( isDivisible( number, i ) )
            {
                return false;
            }
        }
        return true;
}
bool isDivisible (int number, int divisor)
{
    return number % divisor == 0;
}

void factorize_and_sum(int number)
{
    int sum = 0;
    int i = 2;
    while (i < number)
        {
            if(number % i == 0)
            {
                cout << "i=" << i <<" ";
                sum += i;
                number /= i;
                i = 1;
            }
            i++;
        }
        sum += number;
        if (isPrime(sum))
        {
            cout << "number=" << number << "\n";
            cout << "sum of prime factors of " << number << " is: " << sum << "\n";
        }
        else
        {
            cout << "Sum of factors is not prime\n";
        }
        return;
}


The output seems fine, other than the fact that it gives me something like this as well:
"i=2 Sum of factors is not prime".

Granted, I did code in a condition where it'd say "Sum of factors is not prime" if it notices that, but what's with the i=2 in front?

If it's because of the block of code:

1
2
3
4
5
6
7
if(number % i == 0)
            {
                cout << "i=" << i <<" ";
                sum += i;
                number /= i;
                i = 1;
            }
then how do I fix it?
Last edited on
cout << "i=" << i <<" "; and cout << "res=" << res <<"\n";
were used for testing if the code finds all factors correctly.
as the assignment didn't want to see the factors, you can remove those lines.
but if it wanted to see the factors along with the sum, you can modify the output string.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
using namespace std;

int main () {

for(int num=2; num<=20; num++){
	cout << num << "-> ";
	int res=num, sum=0, i=2;
	while(i<res){
		if(res %i == 0){
			cout << i << "+";
			sum +=i; 			
			res /= i;
			i=1;
		}			
		i++;
	}

	if(sum==0) cout << "Prime Number.\n";

	else{		
		cout << res << " = ";
		sum += res; 
		cout << sum << '\n';
	}
}

return 0;
}

output:
2-> Prime Number.
3-> Prime Number.
4-> 2+2 = 4
5-> Prime Number.
6-> 2+3 = 5
7-> Prime Number.
8-> 2+2+2 = 6
9-> 3+3 = 6
10-> 2+5 = 7
11-> Prime Number.
12-> 2+2+3 = 7
13-> Prime Number.
14-> 2+7 = 9
15-> 3+5 = 8
16-> 2+2+2+2 = 8
17-> Prime Number.
18-> 2+3+3 = 8
19-> Prime Number.
20-> 2+2+5 = 9
if wipe out unnecessary calculations, previous program could be optimized.
such as:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main () {
	int minNum = 2;
	int biggestNum = 50;
	vector<int> vec;	
	
	for(int i=2; i<=biggestNum; i++){
		bool b= 1;
		for(auto x: vec){
			if(i%x==0) {
				b=0;
				break;
			}
		}
		if(b) vec.push_back(i);
	}
	
	cout << "vec contains = ";  // all prime numbers in range
	for(auto x: vec) cout << x << " ";
	cout << "\n\n";

	for(int num= minNum; num<=biggestNum; num++){
		int res = num, sum=0;
		cout << num << "-> ";
		auto it = vec.begin();

		while(*it < res){
			if(res % *it ==0){
				cout << *it << "+";
				res /= *it;
				sum += *it;		
				continue;
			}	
			it++;
		}

		if(res==num) cout << "PRIME NUMBER.\n";

		else{			
			sum += res; 
			cout << res << " = "  << sum << " > ";
			if(binary_search(vec.begin(), vec.end(), sum)){
				cout << "Prime\n";
			}
			else{ cout<< "not Prime\n";	}
		}
	}

return 0;
}


output:
vec contains = 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 

2-> PRIME NUMBER.
3-> PRIME NUMBER.
4-> 2+2 = 4 > not Prime
5-> PRIME NUMBER.
6-> 2+3 = 5 > Prime
7-> PRIME NUMBER.
8-> 2+2+2 = 6 > not Prime
9-> 3+3 = 6 > not Prime
10-> 2+5 = 7 > Prime
11-> PRIME NUMBER.
12-> 2+2+3 = 7 > Prime
13-> PRIME NUMBER.
14-> 2+7 = 9 > not Prime
15-> 3+5 = 8 > not Prime
16-> 2+2+2+2 = 8 > not Prime
17-> PRIME NUMBER.
18-> 2+3+3 = 8 > not Prime
19-> PRIME NUMBER.
20-> 2+2+5 = 9 > not Prime
21-> 3+7 = 10 > not Prime
22-> 2+11 = 13 > Prime
23-> PRIME NUMBER.
24-> 2+2+2+3 = 9 > not Prime
25-> 5+5 = 10 > not Prime
26-> 2+13 = 15 > not Prime
27-> 3+3+3 = 9 > not Prime
28-> 2+2+7 = 11 > Prime
29-> PRIME NUMBER.
30-> 2+3+5 = 10 > not Prime
31-> PRIME NUMBER.
32-> 2+2+2+2+2 = 10 > not Prime
33-> 3+11 = 14 > not Prime
34-> 2+17 = 19 > Prime
35-> 5+7 = 12 > not Prime
36-> 2+2+3+3 = 10 > not Prime
37-> PRIME NUMBER.
38-> 2+19 = 21 > not Prime
39-> 3+13 = 16 > not Prime
40-> 2+2+2+5 = 11 > Prime
41-> PRIME NUMBER.
42-> 2+3+7 = 12 > not Prime
43-> PRIME NUMBER.
44-> 2+2+11 = 15 > not Prime
45-> 3+3+5 = 11 > Prime
46-> 2+23 = 25 > not Prime
47-> PRIME NUMBER.
48-> 2+2+2+2+3 = 11 > Prime
49-> 7+7 = 14 > not Prime
50-> 2+5+5 = 12 > not Prime
I think the Practice Problem actually asked to look through all numbers from 1 to 1000. Then add up their prime factors and see if they're prime, and print them if so. We aren't supposed to print the sums that aren't prime. I took a leap of faith and decided to take user's input and check if it's within range of numbers 1 to 1000, rather than looking through all numbers from 1 to 1000. I hope it's allowed. If I have to look all of the numbers physically, I'll try to look for an efficient way to make a numeral array of numbers 1 through 1000, if such a way exists.

Anyway, I'm still getting a funny output. When I input the number 12, it says "2 + 2 +Sum of factors is not prime". Which is not true. How do I get it to also include the 3 in there and print out 7?

Here is the code for the function factorize_and_sum I have now:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void factorize_and_sum(int number)
{
    int sum = 0;
    int i = 2;
    while (i < number)
        {
            if(number % i == 0)
            {
                cout << i <<"+";
                sum += i;
                number /= i;
                i = 1;
            }
            i++;
        }
        if (isPrime(sum))
        {
            cout << "sum of prime factors of " << number << " is: " << sum << "\n";
        }
        else
        {
            cout << "Sum of factors is not prime\n";
        }
        return;
}


And the code for isPrime() and main() respectively:

1
2
3
4
5
6
7
8
9
10
11
bool isPrime (int number)
{
    for ( int i = 2; i < number; i++)
        {
            if ( isDivisible( number, i ) )
            {
                return false;
            }
        }
        return true;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int main ()
{
    int number;
    cout << "Please enter a number to find prime factors of (number must be within range of 1 - 1000): ";
    cin >> number;
    if (number <= 1000)
    {
        if (isPrime(number))
        {
            cout << "Number is already prime\n";
        }
        else if (!isPrime(number))
        {
            factorize_and_sum(number);
        }
    }
    else
    {
        cout << "Input out of range! Please a enter a number equal to or less than 1000\n";
    }
}


Please look through this and tell me what I'm doing wrong.

Just to save your time, I didn't include the code for isDivisible(), as well as the prototypes for the functions, which are there above main().

Edit: When I input 9 just now, it said: "3+sum of prime factors of 3 is: 3". Which is, again, weird.
Last edited on
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
using namespace std;

int main () {	
cout << "The sum of prime factors of the following number's is Prime: \n";
for(int num=2; num<=1000; num++){
	
	int res=num, sum=0, i=2;
	while(i<res){
		if(res %i == 0){			
			sum +=i; 			
			res /= i;
			i=1;
		}			
		i++;
	}

	if(sum) {		
		sum += res; 
		bool b=1;
		for(int i=2; i<sum; i++){
			if(sum%i == 0){
				b=0;
				break;
			} 
		}
		if(b) cout << num << "\n";
	}
}

return 0;
}


output:
The sum of prime factors of the following number's is Prime: 
6
10
12
22
28
34
40
45
48
52
54
56
58
63
75
76
80
82
88
90
96
99
104
108
117
118
136
142
147
148
153
165
172
175
176
184
198
202
207
210
214
224
245
248
250
252
268
273
274
279
294
296
298
300
316
320
325
328
333
345
350
358
360
368
369
376
382
384
385
388
390
394
399
405
412
414
416
420
423
424
432
435
436
448
454
462
464
468
475
477
478
486
488
500
504
507
508
522
536
538
549
550
561
562
567
570
584
595
600
603
608
622
640
651
652
657
660
664
665
675
684
686
694
704
714
715
720
747
759
768
772
775
776
777
792
795
798
808
810
824
833
838
845
847
848
850
856
858
862
864
867
873
885
891
892
903
909
916
922
925
927
930
944
950
954
957
963
972
980
992
I don't want to print out the numbers themselves, just the factors and their sums. But for now, just please let me know of a good way to fix the problem I mentioned in my above post.

Then I have the number to text and text to number programs to ask about as well as a few others. If that's okay. And please don't just give me the code. Provide hints and questions that can point me to the right direction, and/or teach me the stuff. I want to be able to learn how do to it.
Last edited on
I don't want to print out the numbers themselves,
you need to do it. because the problem requires is.

3. Design a program that finds all numbers from 1 to 1000 whose prime factors, when added
together, sum up to a prime number (for example, 12 has prime factors of 2, 2, and 3, which
sum to 7, which is prime). Implement the code for that algorithm.



Edit: When I input 9 just now, it said: "3+sum of prime factors of 3 is: 3". Which is, again, weird.

Not that weird. It's doing exactly what you told it to.

The code in question:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void factorize_and_sum(int number)
{
    int sum = 0;
    int i = 2;
    while (i < number)
        {
            if(number % i == 0)
            {
                cout << i <<"+";
                sum += i;
                number /= i;
                i = 1;
            }
            i++;
        }
        if (isPrime(sum))
        {
            cout << "sum of prime factors of " << number << " is: " << sum << "\n";
        }
        else
        {
            cout << "Sum of factors is not prime\n";
        }
        return;
}


When the function is called with number equal to 9, we loop until i is 3, whereupon we enter the if on line 7. Inside the body of code governed by the if, we set number to 3 via line 11. Since number has changed to 3, the while condition on line 5 will not be true when i reaches 3 again, therefore it will never find the second prime factor (just as it will never find the last prime factor of any number you feed it.)
This is what I mean by not giving me code but trying to give me hints and questions that would lead me to figuring out how to do it (@anup30).

Alright, so how do I fix this?

And right now, this is what I have (I changed main() a little, and I used isPrime() for the check in the if condition on Line 7 (Line 55 in the actual code).

I still need to fix the problem, though, of course. But I'll need to learn from you guys how to do that (and I do mean "learn", not just "copy").

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <iostream>
#include <math.h>

// function prototypes

bool isDivisible (int number, int divisor);

bool isPrime (int number);

void factorize_and_sum(int number);

using namespace std;

int main ()
{
    int number;
    cout << "Enter a number less than or equal to 1000 to be factored: ";
    cin >> number;
    if (number > 0 && number <= 1000)
    {
        if (!isPrime(number))
        {
            factorize_and_sum(number);
        }
        else if (isPrime(number))
        {
            cout << "The number entered is already prime\n";
        }
    }
    else
    {
        cout << "Invalid input! Please enter a number less than or equal to 1000\n";
    }
}

bool isPrime (int number)
{
    for (int i = 2; i < sqrt((double)number); i++)
    {
        if (isDivisible(number, i))
        {
            return false;
        }
    }
    return true;
}

bool isDivisible (int number, int divisor)
{
    return number % divisor == 0;
}

void factorize_and_sum(int number)
{
    int sum = 0;
    int i = 2;
    while (i < number)
    {
        if(!isPrime(number))
        {
            cout << i <<"+";
            sum += i;
            number /= i;
            i = 1;
        }
        i++;
    }
    if (isPrime(sum))
    {
        cout << "sum of prime factors of " << number << " is: " << sum << "\n";
    }
    else
    {
        cout << "Sum of factors is not prime\n";
    }
    return;
}


Please help me fix it.

Since the actual practice problem asked to find the numbers amongst the first 1000 numbers whose prime factors add up to a prime number, I need a good and efficient way t use an array variable to store the 1000 numbers and iterate over them in main() to find the numbers I need.

The place I where I am in the book right now, it hasn't gotten to saying anything about the <algorithm> and <vector> header files. So I don't know about any functions from those files yet, and while I could Google them, right now I want to do this with the info in <iostream>.
Ok I help you fixing this.

1. take a pen and paper
2. write down what you want to have
3. write down a rough plan of how you want to accomplish that goal
4. go in more details
5. ???
6. profit

it could look like this

1. *poor guy without pen and paper*
2. print all numbers between 1 and 1000 and their prime factors where the sum of the prime factors is a prime
3. loop through all numbers from 1 to 1000 and get the prime factorsof the number, then add the factors up and see if the sum is a prime
4. loop through all numbers from 1 to 1000 and get the prime factors of the number by looping from 2 to the square root of the number and check if there is a rest when dividing the number with the current number.
If a Factor is found make sure you check the same number again because one prime factor may occure more than once.
Also make sure to divide the number by the current prime factor, otherwise the factor will allways be found.

When a prime factor is found store it somewhere or just add it to the sum.
when finished check if the sum of the found prime factors is a Prime.

if it is a prime print the number and the sum of the prime factors (or if stored also print all primefactors)

5. ???
6. profit
It's the factorization and adding factors together with a loop parts and I don't get right now, and the code people have posted here doesn't help since I can't really tell what's really going on with the divisions and additions there.

So I don't get how to do number 3, first of all. And I can already do the beginning bit of number 4, but the prime factor part is where I get lost. So start helping from there.

And again, ask me questions and give me hints about the pseudocode and algorithm, as well as the math expressions (keeping in mind the variables and functions I've got in my program already, please) that I should use in the program.

I'll try to answer the questions I ask, and they have to be about the program and have to have answers that lead to solution of the problem I'm trying to solve.
Pages: 12