Algorithms/prime_factoriz.cpp at master · Tejas988/Algorithms · GitHub

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

int p[1000001]={0};
void printFactor(int n)
{

	vector<pair<int,int>> factor;
	for(int i=2;i*i<n;i++)//will go till root n
	{
		if(n%i==0)
		{	int cnt=0;
			while(n%i==0)//count no of times it is divided by that prime factor
			{
				n/=i;
				cnt++;

			}
		 factor.push_back({i,cnt});
		}
	}
	if(n!=1)//means the remaining part itself is prime
	{
		factor.push_back({n,1});
	}
	for(auto x:factor)
	{
		cout<<x.first<<"-"<<x.second<<endl;
	}
}


//using sieve (mostly used in queries)

vector<int> prime_sieve()
{
	for(int i=3;i<=1000000;i+=2)
		p[i]=1;
	for(ll i=3;i<=1000000;i++)
	{
		if(p[i])
		{
			for(ll j=i*i;j<=1000000;j+=i)
				p[j]=0;
		}
	}
	p[2]=1;
	p[1]=p[0]=0;
	vector<int> v;
	for(int i=0;i<=10000;i++)
	{
		if(p[i])
			v.push_back(i);
	}
	return v;
}

void factorize(int n,vector<int> &primes)
{
	vector<pair<int,int>> factor;
	int i=0;
	int p=primes[i];
		while(p*p<=n)
		{
			if(n%p==0)
			{
				int cnt=0;
				while(n%p==0)
				{
					n/=p;
					cnt++;
				}
				factor.push_back({p,cnt});
			}
			i++;
			p=primes[i];
		}
		if(n!=1)
			factor.push_back({n,1});
	for(auto x:factor)
	{
		cout<<x.first<<"-"<<x.second<<endl;
	}

}
int noOfDivisors(int n,vector<int> &primes)
{
	int ans=1;
	int i=0;
	int p=primes[i];
		while(p*p<=n)
		{
			if(n%p==0)
			{
				int cnt=0;
				while(n%p==0)
				{
					n/=p;
					cnt++;
				}
				ans*=(++cnt);
			}
			i++;
			p=primes[i];
		}
		if(n!=1)
			ans*=2;
	return ans;

}


int main()
{
	#ifndef ONLINE_JUDGE
		freopen("input.txt","r",stdin);
		freopen("output1.txt","w",stdout);
	#endif
	vector<int> primes;
	primes=prime_sieve();
	cout<<noOfDivisors(10,primes);
	return 0;
}