블로그 이사 중입니다 >> gumgood.github.io

Efficient program to print all prime factors of a given number 본문

Problem Solving/분류없음

Efficient program to print all prime factors of a given number

gumgood 2020. 2. 11. 16:21

원문 : https://www.geeksforgeeks.org/print-all-prime-factors-of-a-given-number/

 

Following are the steps to find all prime factors.

1) While n is divisible by 2, print 2 and divide n by 2.

2) After step 1, n must be odd, Now start a loop from i=3 to square root of n. While i divides n, print i and divide n by i. After i fails to divide n, increment i by 2 and continue.

3) If n is a prime number and is greater than 2, then n will not become 1 by above two steps. So print n if it is greater than 2.

 

// C++ program to print all prime factors 
#include <bits/stdc++.h> 
using namespace std; 

// A function to print all prime 
// factors of a given number n 
void primeFactors(int n) 
{ 
	// Print the number of 2s that divide n 
	while (n % 2 == 0) 
	{ 
		cout << 2 << " "; 
		n = n/2; 
	} 

	// n must be odd at this point. So we can skip 
	// one element (Note i = i +2) 
	for (int i = 3; i <= sqrt(n); i = i + 2) 
	{ 
		// While i divides n, print i and divide n 
		while (n % i == 0) 
		{ 
			cout << i << " "; 
			n = n/i; 
		} 
	} 

	// This condition is to handle the case when n 
	// is a prime number greater than 2 
	if (n > 2) 
		cout << n << " "; 
} 

/* Driver code */
int main() 
{ 
	int n = 315; 
	primeFactors(n); 
	return 0; 
} 

// This is code is contributed by rathbhupendra 

 

How does this work?

The steps 1 and 2 take care of composite numbers and step 3 takes care of prime numbers. To prove that the complete algorithm works, we need to prove that steps 1 and 2 actually take care of composite numbers. This is clear that step 1 takes care of even numbers. And after step 1, all remaining prime factor must be odd (difference of two prime factors must be at least 2), thist explains why i is incremented by 2. Now the main part is, the loop runs till square root of n not til n. To prove that this optimization works, let us consider the following property of composite number.

Every composite number has al least one prime factor less than or equal to square root of itself. This property can be proved using counter statement. Let a and b two factors of n such that a*b = n. If both are greater than \(sqrt(n)\) then a, ~

 

0 Comments
댓글쓰기 폼