C++

Forum

 
what's wrong with my code?

sultan0104 (12)
Hi im trying to make a program to prime factorize a positive integer, but it doesnt seem to work. Can you help me find whats wrong with it?

#include <cstdio>
using namespace std;

bool prime(int x) {
if (x < 2) {
return false;
}
for (int i = 2; i*i <= x; i++) {
if (x % i == 0) {
return false;
}
}
return true;
}

void PF(int &y) {
int pMax = 0;
int ar[1000001] = {0};

while (y > 1) {
for (int p = 2; p <= y; p++) {
if (prime(p) && y % p == 0) {
if (p > pMax) {
pMax = p;
}
ar[p]++;
y = y/p;
break;
}
}
}

for (int p = 2; p <= y; p++) {
if (p == pMax) {
if (ar[pMax] > 1) {
printf("%d^%d", p, ar[p]);
} else if (ar[pMax] == 1) {
printf("%d", p);
}
} else {
if (ar[p] > 1) {
printf("%d^%d × ", p, ar[p]);
} else if (ar[p] == 1) {
printf("%d × ", p);
}
}
}
}

int main() {
int N;
scanf("%d", &N);
PF(N);
}
lastchance (6980)
Please put your code in code tags so that we can read it. Also, give something more explanatory than “it doesn’t work”.

I doubt whether your search loop will be able to pick up repeated prime factors.

If you are picking off factors from the lowest first then you DON’T have to test that they are individually prime because you have already picked off lower factors.

Until you put your code in code tags so that we can see indentation and loop structure I would refrain from further comment.
sultan0104 (12)
Hi, thanks for replying. By "it doesn't work" I mean when I run the code, it doesn't show any errors in my code but it won't give any outputs at all, just blank. I'm sorry, but can you please tell me how to put my code in code tags? I'd really appreciate it
sultan0104 (12)
Oh wait I think I can

Here's the 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
 
#include <cstdio>
using namespace std;

bool prime(int x) {
	if (x < 2) {
		return false;
	}
	for (int i = 2; i*i <= x; i++) {
		if (x % i == 0) {
			return false;
		}
	}
	return true;
}

void PF(int &y) {
	int pMax = 0;
	int ar[1000001] = {0};
	
	while (y > 1) {
		for (int p = 2; p <= y; p++) {
			if (prime(p) && y % p == 0) {
				if (p > pMax) {
					pMax = p;
				}
				ar[p]++;
				y = y/p;
				break;
			}
		}
	}
	
	for (int p = 2; p <= y; p++) {
		if (p == pMax) {
			if (ar[pMax] > 1) {
				printf("%d^%d", p, ar[p]);
			} else if (ar[pMax] == 1) {
				printf("%d", p);
			}
		} else {
			if (ar[p] > 1) {
				printf("%d^%d × ", p, ar[p]);
			} else if (ar[p] == 1) {
				printf("%d × ", p);
			}
		}
	}
}

int main() {
	int N;
	scanf("%d", &N);
	PF(N);
}



I actually edited the code but it still didn't give the output I was hoping 

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
 
#include <cstdio>
using namespace std;

bool prime(int x) {
	if (x < 2) {
		return false;
	}
	for (int i = 2; i*i <= x; i++) {
		if (x % i == 0) {
			return false;
		}
	}
	return true;
}

int main() {
	int N;
	scanf("%d", &N);
	int pMax = 0;
	int ar[1000001] = {0};
	
	if (N == 1) {
		printf("%d", N);
	} else {
		for (int i = 2; i <= N; i++) {
			if (prime(i)) {
				while (N % i == 0) {
					N = N/i;
					ar[i]++;
					if (i > pMax) {
						pMax = i;
					}
				}
			} else {
				continue;
			}
		}
	}
	
	for (int i = 2; i <= N; i++) {
		if (ar[i] == 1) {
			if (i != pMax) {
				printf("%d × ", i);
			} else {
				printf("%d", i);
			}
		} else if (ar[i] > 1) {
			if (i != pMax) {
				printf("%d^%d × ", i, ar[i]);
			} else {
				printf("%d^%d", i, ar[i]);
			}
		}
	}
}


Thank you so much for helping me
Last edited on
lastchance (6980)
You can either edit your original post or create a new one and then use the Format menu (the first item in <>). This will put the requisite tags in for you.

The format menu doesn’t function for an initial post, so either edit that quickly or manually put the tags in. You will see what they are once you have used the format menu.
seeplus (6591)

[code]
    formatted code goes here
[/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
 
#include <cstdio>
using namespace std;

bool prime(int x) {
	if (x < 2) {
		return false;
	}

	for (int i = 2; i * i <= x; i++) {
		if (x % i == 0) {
			return false;
		}
	}

	return true;
}

void PF(int& y) {
	int pMax = 0;
	int ar[1000001] = {0};

	while (y > 1) {
		for (int p = 2; p <= y; p++) {
			if (prime(p) && y % p == 0) {
				if (p > pMax) {
					pMax = p;
				}

				ar[p]++;
				y = y / p;
				break;
			}
		}
	}

	for (int p = 2; p <= y; p++) {
		if (p == pMax) {
			if (ar[pMax] > 1) {
				printf("%d^%d", p, ar[p]);
			} else if (ar[pMax] == 1) {
				printf("%d", p);
			}
		} else {
			if (ar[p] > 1) {
				printf("%d^%d × ", p, ar[p]);
			} else if (ar[p] == 1) {
				printf("%d × ", p);
			}
		}
	}
}

int main() {
	int N;
	scanf("%d", &N);
	PF(N);
}


L20. This size array on the stack?? Either make ar a std:vector/array or make static or global.

Is this C or C++ code? The first 2 lines indicate C++ - but the rest of the cod is C.
Last edited on
sultan0104 (12)
This is C++, maybe it looks like C because I've only learned the basics(started learning about 5 days ago). I'm sorry but I don't understand any of your suggested solutions, I haven't learnt that far 😭 it's ok tho, I will try to find another way to solve this problem
zapshe (1907)
This is C++, maybe it looks like C because I've only learned the basics

printf is more of a C way of outputting things to the console. 

 
 
cout << p << "^" << ar[p];


cout, as shown, is the modern C++ way to output to the screen. scanf is also C, with C++ using std::cin >>:

1
2
3
4
5
6
 
int main()
{
	int N;
	cin >> N;
	PF(N);
}



You're also using "#include <cstdio>", which gives you access to the C library. Whatever tutorial you're following is NOT taking advantage of C++'s features and benefits over C.

Prime factorization isn't as complex as your code is making it, you can look at a reference here:

https://www.geeksforgeeks.org/print-all-prime-factors-of-a-given-number/
againtry (2313)
@OP

2 things:

1. main should look like this otherwise all you produce is a blinking cursor.
1
2
3
4
5
6
7
8
 
int main()
{
    int N;
    printf ("Enter a number: ");
    scanf("%d", &N);
    
    PF(N);
}


2. To get the prime factors then consider the following as a straight forward way. (It doesn't mean you have to copy it but draw on the ideas.)
https://www.geeksforgeeks.org/prime-factor/

lastchance (6980)
@sultan04,
You keep dividing y by p, so that eventually it is likely to be 1. Thus your second major loop (limited by p<=y) is unlikely ever to run and so it won’t print anything.

There is no need to tick off found prime factors in ar[]. If you want to put anything in that array ... put your prime factors in it!

Your method is flawed. As I said earlier, you will fail to pick up repeated prime factors and you do NOT explicitly have to check whether a potential factor is prime because you have already covered any smaller factors.

Please re-think your method. A good way would be to do it by hand. Try factorising 360 (which is 2*2*2*3*3*5) and also 13 (which is prime).
seeplus (6591)
prime factorize a positive integer


Is there a limit on this value? One way would be to have a table of primes to use rather than calculating primes.
jonnin (11437)
factoring numbers is considered a difficult problem .. some encryption is based off that idea, that finding one of the 2 factors of 2 gigantic prime numbers multiplied together is aggravating.
whatever you do is likely going to end up being brute force:

for all the prime numbers up to the sqrt of the number,
see if it will divide into the number. If it does, try again until it won't. Update number each time by dividing by the factor you found.
so to factor all unsigned 64 bit integers, you can find all the primes that fit in 32 bits (this is PDQ on today's computers with a good sieve), and then just crunch along.

you can find the factors (but not prime factors) very quickly up to 100 or maybe a bit beyond with std::gcd and a couple of magic constants:
614889782588491410ULL
3749562977351496827ULL
which is really effective for typical non crypto use cases of small numbers with lots of 2,3,5,7 factors. Numbers that don't have a factor in 2-100 will end up back in the brute force loops.
Last edited on
Manga (1030)
This seems to work for me.

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


int main() {
    
   cout << "Enter a number. ";
   long int x;
   cin >> x;
   cout << endl;
   
   for(int i = 2; i <= x/2; i++) {
       if(x%i == 0) {
           cout << i;
           cout << "*";
           x = x/i;
           i = 1;
       }
       else if(i >= 3) {
          i++;   
       }
   }
   cout << x;
}
Last edited on
lastchance (6980)
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
 
#include <iostream>
#include <vector>
using namespace std;

vector<unsigned long long> factorise( unsigned long long N )
{
   vector<unsigned long long> result;   if ( N <= 1 ) return result;

   for ( unsigned long long i = 2; i * i <= N; i += 1 + ( i > 2 ) )
   {
      while ( N % i == 0 )
      {
         result.push_back( i );
         N /= i;
      }
   }
   if ( N > 1 ) result.push_back( N );
   return result;
}

int main()
{
   unsigned long long tests[] = { 2, 9, 13, 169, 360, 3600, 12345678910111213 };
   for ( auto N : tests )
   {
      cout << N << " =";
      int num = 0;
      for ( auto e : factorise( N ) ) cout << ( ++num == 1 ? " " : " x " ) << e;
      cout << '\n';
   }
}


2 = 2 
9 = 3 x 3 
13 = 13 
169 = 13 x 13 
360 = 2 x 2 x 2 x 3 x 3 x 5 
3600 = 2 x 2 x 2 x 2 x 3 x 3 x 5 x 5 
12345678910111213 = 113 x 125693 x 869211457

Last edited on
againtry (2313)
And to be precise every number, prime or non-prime, has itself and 1 as factors.
sultan0104 (12)
Thanks a lot guys, it's working just as I hoped now. I still don't know what I did wrong in my code but I've found a new code that doesnt include a 1000001 sized array, in fact I didnt need to check if the divisor is a prime at all cuz once a number has been factorized completely by its prime factors (starting from 2,3,so on) the number wont be divisible by their multiples anymore hehe
sultan0104 (12)
@lastchance

Omg that makes senseee thats why it didnt work beforeee the y will have already become 1 once ive done running the first loop, thats why the next loop doesnt run, since p = 2 which is > y = 1... thank you so much this kept me up at night lol
Last edited on
Topic archived. No new replies allowed.