LightOJ – Intelligent Factorial Factorization

L
Problem NameIntelligent Factorial Factorization
JudgeLightOJ
Problem Linkhttps://lightoj.com/problem/intel-factor-factorization
Algorithms & DSPrime Factorization
#include<bits/stdc++.h> using namespace std; typedef long long ll; bitset<110>bs; vector<ll>primes; ll facts[110][50]; void sieve(ll ub) { bs.set(); bs[0]=bs[1]=0; primes.push_back(2); for(ll i=4;i<=ub;i+=2)bs[i]=0; for(ll i=3;i<=ub;i+=2){ if(bs[i]){ for(ll j=i*i;j<=ub;j+=(2*i))bs[j]=0; primes.push_back(i); } } } void inis() { for(ll i=0;i<=100;i++){ for(ll j=0;j<50;j++){ facts[i][j]=0; } } } int main() { sieve(110); inis(); ll pLen=primes.size(); for(ll i=2;i<=100;i++){ ll num=i; for(ll j=0;j<pLen;j++)facts[i][j]=facts[i-1][j]; for(ll j=0;primes[j]*primes[j]<=num;j++){ ll ct=0; while(num%primes[j]==0){ ct++; num/=primes[j]; } facts[i][j]+=ct; } if(num>1){ ll idx=upper_bound(primes.begin(),primes.end(),num)-primes.begin(); idx--; facts[i][idx]+=1; } } ll t; cin>>t; for(ll T=1;T<=t;T++){ ll n; cin>>n; cout<<"Case "<<T<<": "<<n<<" ="; ll ck=0; for(ll i=0;i<pLen;i++){ if(facts[n][i]){ if(!ck)ck++; else cout<<" *"; cout<<" "<<primes[i]<<" ("<<facts[n][i]<<")"; } } cout<<"\n"; } return 0; }
Code language: PHP (php)

About the author

আবু রিফাত মুহাম্মদ

সখের বশে প্রোগ্রামিং করি। নতুন নতুন জিনিস শিখতে এবং শেখাতে ভালবাসি।

Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments

আবু রিফাত মুহাম্মদ

সখের বশে প্রোগ্রামিং করি। নতুন নতুন জিনিস শিখতে এবং শেখাতে ভালবাসি।

যোগাযোগ করুন

error: Alert: Content is protected !!