Prime Factors Finding

Algorithm:

1) divide n by 2 till n is divided by 2 and save 2 in a list each time
2) divide n by (3 to  root(n) and only the odd numbers) if divisible save it in the list
3)if n is greater than 2 save n in the list

all the prime factors are in the list.




Code:

	#include<bits/stdc++.h>
	using namespace std;
	vector<int>pfactors;
	void primefactors(int n) {
	while (n%2 == 0){
	pfactors.push_back(2);
	n = n/2;
	}
	for (int i = 3; i <= sqrt(n); i = i+2){
	while (n%i == 0){
	pfactors.push_back(i);
	n = n/i;
	}
	}
	if (n > 2) pfactors.push_back(n);
	}
	int main() {
	int n;
	cin>>n;
	primefactors(n);
	for(int i=0;i<pfactors.size();i++){
	cout<<pfactors[i]<<" ";
	}
	return 0;
	}

view raw primefactorfinding.cpp hosted with ❤ by GitHub