fac:Pls help for this programing problem in c++ (standard IO without file read/w
ID: 3915026 • Letter: F
Question
fac:Pls help for this programing problem in c++ (standard IO without file read/write),better with some comment about why coding that way,thanks
Problem A: Factorization Time limit: 2 sec. Problem Description Write a program to factor a number. All the prime factors should be listed in increasing order, and the power should be listed. Input Format The first line contains an integer n which indicates the number of test cases. Each of the next n lines is a test case which contains a positive number N, 1NExplanation / Answer
Solution:
#include "bits/stdc++.h"
#include<map>
using namespace std;
#define MAXN 99999999
//stores smallest prime factor for every number
int smallestprimefactor[MAXN];
// Calculating SPF (Small Prime Factor) for every
// number till MAXN.
void sieve()
{
smallestprimefactor[1] = 1;
for (int i=2; i<MAXN; i++)
// marking smallest prime factor for every
// number to be itself.
smallestprimefactor[i] = i;
// separately marking spf for every even
// number as 2
for (int i=4; i<MAXN; i+=2)
smallestprimefactor[i] = 2;
for (int i=3; i*i<MAXN; i++)
{
// checking if i is prime
if (smallestprimefactor[i] == i)
{
// marking SPF for all numbers divisible by i
for (int j=i*i; j<MAXN; j+=i)
// marking spf[j] if it is not
// previously marked
if (smallestprimefactor[j]==j)
smallestprimefactor[j] = i;
}
}
}
// by dividing by smallest prime factor at every step
std::map<int, int> Factorization(int x)
{
std::map<int, int> mret;
while (x != 1)
{
mret[smallestprimefactor[x]]++;
x = x / smallestprimefactor[x];
}
return mret;
}
// driver program for above function
int main(int argc, char const *argv[])
{
// precalculating Smallest Prime Factor
sieve();
int Testcase;
cin >> Testcase;
for(int i = 0; i < Testcase; i++)
{
int x;
cin >> x;
cout << "prime factorization for " << x << " : ";
// calling Factorization function
std::map<int, int> p = Factorization(x);
int count = 0;
for(auto item : p)
{
cout << item.first << "^" << item.second ;
if(p.size() != ++count)
cout << " * ";
}
cout << endl;
}
return 0;
}
output:
3
99999989
prime factorization for 99999989 : 99999989^1
99999984
prime factorization for 99999984 : 2^4 * 3^1 * 7^2 * 17^1 * 41^1 * 61^1
99999947
prime factorization for 99999947 : 4013^1 * 24919^1
#include "bits/stdc++.h"
#include<map>
using namespace std;
#define MAXN 99999999
//stores smallest prime factor for every number
int smallestprimefactor[MAXN];
// Calculating SPF (Small Prime Factor) for every
// number till MAXN.
void sieve()
{
smallestprimefactor[1] = 1;
for (int i=2; i<MAXN; i++)
// marking smallest prime factor for every
// number to be itself.
smallestprimefactor[i] = i;
// separately marking spf for every even
// number as 2
for (int i=4; i<MAXN; i+=2)
smallestprimefactor[i] = 2;
for (int i=3; i*i<MAXN; i++)
{
// checking if i is prime
if (smallestprimefactor[i] == i)
{
// marking SPF for all numbers divisible by i
for (int j=i*i; j<MAXN; j+=i)
// marking spf[j] if it is not
// previously marked
if (smallestprimefactor[j]==j)
smallestprimefactor[j] = i;
}
}
}
// by dividing by smallest prime factor at every step
std::map<int, int> Factorization(int x)
{
std::map<int, int> mret;
while (x != 1)
{
mret[smallestprimefactor[x]]++;
x = x / smallestprimefactor[x];
}
return mret;
}
// driver program for above function
int main(int argc, char const *argv[])
{
// precalculating Smallest Prime Factor
sieve();
int Testcase;
cin >> Testcase;
for(int i = 0; i < Testcase; i++)
{
int x;
cin >> x;
cout << "prime factorization for " << x << " : ";
// calling Factorization function
std::map<int, int> p = Factorization(x);
int count = 0;
for(auto item : p)
{
cout << item.first << "^" << item.second ;
if(p.size() != ++count)
cout << " * ";
}
cout << endl;
}
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.