C++

Forum

 
Getting Prime Factors of first 1000 numbers

Pages: 12
anup30 (968)
well. cire explained how to fix that. if you ask for even more explicit answer ....
you sound like point 1 of Gamer2015.

may be you should build your knowledge ground up.

task 1: merge isDivisible function with isPrime function. (so you will have only one function outside main)
DragonOsman (715)
I'm posting the latest version now; the output seems fine except for how it's showing 1000 as 31 (the sum of the factors is 41, though, which seems to be correct).

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
 
#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 ()
{
    for (int i = 0; i <= 1000; i++)
    {
        if (!isPrime(i))
        {
            factorize_and_sum(i);
        }
        else
        {
            cout << "Number is prime\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 <<" ";
            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;
}
Last edited on
Gamer2015 (810)
the output seems fine except for how it's showing 1000 as 31

the sum of the prime factors of 1000 should be 21

2*5 = 10; 1000 = (2*5)^3)
(2*5)*(2*5) = 100
(2*5)*(2*5)*(2*5) = 1000
7 + 7 + 7 = 21

It's the factorization and adding factors together with a loop parts and I don't get right now

Well, you know what, if you don't get it than just split it up again :)
make a function that returns all factors and then work with them the way you like

all of this may look like that
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
 
#include <iostream>
#include <vector>
#include <cmath>

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

std::vector<int> getPrimeFactors(int number)
{
    int max = sqrt(number);
    std::vector<int> primes;

    for(int i = 2; i <= max; ++i) // loop through same numbers as isPrime to get prime factors
    {
	if(isPrime(number)) // check if the number is a prime Factor
	{
	    primes.push_back(number); // add element to container
	    break; // break for-loop
        }

	if(isPrime(i)) // if it is a prime
	{
	    if(isDivisable(number, i)) // and divisable, then it is a prime factor of number
	    {
		number /= i;
		primes.push_back(i); // add element to container

		i--; // check same factor again
	    }
        }
    }
    return primes;
}

int main(void)
{
    for(int i = 0; i <= 1000; ++i)
    {
        if(isPrime(i))
        {
            std::cout << i << " -> is a Prime." << std::endl;
        }
        else
        {
            std::vector<int> factors; // a C++ Container class
            factors = getPrimeFactors(i); 

// do the printing work
            int sum = 0;
            
            std::cout << i << ': '; 
            for(int i = 0; i < factors.size(); ++i) 
            {
                std::cout << factors[i] << ' '; // print the factors
                sum += factors[i]; // add the factors up
            }
            std::cout << " = " << sum << " -> ";

            if(isPrime(sum))
                std::cout << "sum of factors is a Prime";
            else
                std::cout << "sum of factors is not a Prime";
        
            std::cout << std::endl;
        }
    }
}
anup30 (968)
much faster version of my previous 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
 
#include <iostream>
#include <cmath>

int main () {	
std::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;
	int rootres = sqrt(res);
	while(i<=rootres){
		if(res %i == 0){			
			sum +=i;
			res /= i;
			rootres = sqrt(res);
			continue;
		}			
		i++;
	}
	if(sum) {		
		sum += res; 
		bool b=1;
		int rootsum = sqrt(sum);
		for(int i=2; i<=rootsum; i++){
			if(sum%i == 0){
				b=0;
				break;
			} 
		}
		if(b) std::cout << num << "\n";
	}
}

return 0;
}
anup30 (968)
with factors:
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
 
#include <iostream>
#include <cmath>
#include <string>
int main () {	

std::cout << "The sum of prime factors of the following number's is Prime: \n";
std::string s;

for(int num=2; num<=1000; num++){	
	int res=num, sum=0, i=2;
	int rootres = sqrt(res);
	s = "";
	while(i<=rootres){
		if(res %i == 0){
			s += std::to_string(i) + "+";			
			sum +=i;
			res /= i;
			rootres = sqrt(res);
			continue;
		}			
		i++;
	}
	if(sum) {	
		s += std::to_string(res) + "= ";	
		sum += res; 
		bool b=1;
		int rootsum = sqrt(sum);
		for(int i=2; i<=rootsum; i++){
			if(sum%i == 0){
				b=0;
				break;
			} 
		}
		if(b) std::cout << num << ": " << s << sum << "\n";
	}
}

return 0;
}


output:
The sum of prime factors of the following number's is Prime: 
6: 2+3= 5
10: 2+5= 7
12: 2+2+3= 7
22: 2+11= 13
28: 2+2+7= 11
34: 2+17= 19
40: 2+2+2+5= 11
45: 3+3+5= 11
48: 2+2+2+2+3= 11
52: 2+2+13= 17
54: 2+3+3+3= 11
56: 2+2+2+7= 13
58: 2+29= 31
63: 3+3+7= 13
75: 3+5+5= 13
76: 2+2+19= 23
80: 2+2+2+2+5= 13
82: 2+41= 43
88: 2+2+2+11= 17
90: 2+3+3+5= 13
96: 2+2+2+2+2+3= 13
99: 3+3+11= 17
104: 2+2+2+13= 19
108: 2+2+3+3+3= 13
117: 3+3+13= 19
118: 2+59= 61
136: 2+2+2+17= 23
142: 2+71= 73
147: 3+7+7= 17
148: 2+2+37= 41
153: 3+3+17= 23
165: 3+5+11= 19
172: 2+2+43= 47
175: 5+5+7= 17
176: 2+2+2+2+11= 19
184: 2+2+2+23= 29
198: 2+3+3+11= 19
202: 2+101= 103
207: 3+3+23= 29
210: 2+3+5+7= 17
214: 2+107= 109
224: 2+2+2+2+2+7= 17
245: 5+7+7= 19
248: 2+2+2+31= 37
250: 2+5+5+5= 17
252: 2+2+3+3+7= 17
268: 2+2+67= 71
273: 3+7+13= 23
274: 2+137= 139
279: 3+3+31= 37
294: 2+3+7+7= 19
296: 2+2+2+37= 43
298: 2+149= 151
300: 2+2+3+5+5= 17
316: 2+2+79= 83
320: 2+2+2+2+2+2+5= 17
325: 5+5+13= 23
328: 2+2+2+41= 47
333: 3+3+37= 43
345: 3+5+23= 31
350: 2+5+5+7= 19
358: 2+179= 181
360: 2+2+2+3+3+5= 17
368: 2+2+2+2+23= 31
369: 3+3+41= 47
376: 2+2+2+47= 53
382: 2+191= 193
384: 2+2+2+2+2+2+2+3= 17
385: 5+7+11= 23
388: 2+2+97= 101
390: 2+3+5+13= 23
394: 2+197= 199
399: 3+7+19= 29
405: 3+3+3+3+5= 17
412: 2+2+103= 107
414: 2+3+3+23= 31
416: 2+2+2+2+2+13= 23
420: 2+2+3+5+7= 19
423: 3+3+47= 53
424: 2+2+2+53= 59
432: 2+2+2+2+3+3+3= 17
435: 3+5+29= 37
436: 2+2+109= 113
448: 2+2+2+2+2+2+7= 19
454: 2+227= 229
462: 2+3+7+11= 23
464: 2+2+2+2+29= 37
468: 2+2+3+3+13= 23
475: 5+5+19= 29
477: 3+3+53= 59
478: 2+239= 241
486: 2+3+3+3+3+3= 17
488: 2+2+2+61= 67
500: 2+2+5+5+5= 19
504: 2+2+2+3+3+7= 19
507: 3+13+13= 29
508: 2+2+127= 131
522: 2+3+3+29= 37
536: 2+2+2+67= 73
538: 2+269= 271
549: 3+3+61= 67
550: 2+5+5+11= 23
561: 3+11+17= 31
562: 2+281= 283
567: 3+3+3+3+7= 19
570: 2+3+5+19= 29
584: 2+2+2+73= 79
595: 5+7+17= 29
600: 2+2+2+3+5+5= 19
603: 3+3+67= 73
608: 2+2+2+2+2+19= 29
622: 2+311= 313
640: 2+2+2+2+2+2+2+5= 19
651: 3+7+31= 41
652: 2+2+163= 167
657: 3+3+73= 79
660: 2+2+3+5+11= 23
664: 2+2+2+83= 89
665: 5+7+19= 31
675: 3+3+3+5+5= 19
684: 2+2+3+3+19= 29
686: 2+7+7+7= 23
694: 2+347= 349
704: 2+2+2+2+2+2+11= 23
714: 2+3+7+17= 29
715: 5+11+13= 29
720: 2+2+2+2+3+3+5= 19
747: 3+3+83= 89
759: 3+11+23= 37
768: 2+2+2+2+2+2+2+2+3= 19
772: 2+2+193= 197
775: 5+5+31= 41
776: 2+2+2+97= 103
777: 3+7+37= 47
792: 2+2+2+3+3+11= 23
795: 3+5+53= 61
798: 2+3+7+19= 31
808: 2+2+2+101= 107
810: 2+3+3+3+3+5= 19
824: 2+2+2+103= 109
833: 7+7+17= 31
838: 2+419= 421
845: 5+13+13= 31
847: 7+11+11= 29
848: 2+2+2+2+53= 61
850: 2+5+5+17= 29
856: 2+2+2+107= 113
858: 2+3+11+13= 29
862: 2+431= 433
864: 2+2+2+2+2+3+3+3= 19
867: 3+17+17= 37
873: 3+3+97= 103
885: 3+5+59= 67
891: 3+3+3+3+11= 23
892: 2+2+223= 227
903: 3+7+43= 53
909: 3+3+101= 107
916: 2+2+229= 233
922: 2+461= 463
925: 5+5+37= 47
927: 3+3+103= 109
930: 2+3+5+31= 41
944: 2+2+2+2+59= 67
950: 2+5+5+19= 31
954: 2+3+3+53= 61
957: 3+11+29= 43
963: 3+3+107= 113
972: 2+2+3+3+3+3+3= 19
980: 2+2+5+7+7= 23
992: 2+2+2+2+2+31= 41
Topic archived. No new replies allowed.
Pages: 12