প্রাইম ফ্যাক্টরাইজেশন বের করার জন্য কিছু কোড

প্রাইম ফ্যাক্টরাইজেশন বের করার জন্য  এই কোডটা আমার কাছে অনেক সহজ মনে হয়। তবে এটা বড় সংখ্যার ক্ষেত্রে  সিভ অব ইরাথোসথেনেস এর মত কাজ করে।

#include<bits/stdc++.h>
#define ll long long
using namespace std;
bool is_prime(long n)
{
    if(n<2){
        return false;
    }
    for(long i=2; i*i<=n; i++)
    {
        if((n%i)==0){
            return false;
        }
    }
    return true;
}
int main ()
{
    long num;
    cin >> num;
    cout << "prime factor number are " << num << ": ";
    for(int i=0; i<=num; i++){
        if(is_prime(i) && num%i==0){
            cout << i << ' ';
        }
    }
}

#কোড 2:

#include<bits/stdc++.h>
using namespace std;
void prime_factor(int n)
{
    while(n%2==0)
    {
        printf("%d ", 2);
        n=n/2;
    }
    for(int i=3; i<=sqrt(n); i=i+2)
    {
        while(n%i==0)
        {
            printf("%d ", i);
            n=n/i;
        }
    }
    if(n>2){
        printf("%d ", n);
    }
}

int main()
{
    int n;
    cin >> n;
    prime_factor(n);
    return 0;
}

# মাল্টিপল ক্যুয়েরির মাধ্যমে প্রাইম ফ্যাক্টরাইজেশন নির্নয় করা।

#include<bits/stdc++.h>
#define ll long long
#define mx  100001
using namespace std;

int spf[mx]; ///spf = sieve of power factorization
void sieve()
{
    spf[1] = 1;
    //generate for every prime factor
    for (int i=2; i<mx; i++){
        spf[i] = i;
    }
    //generate for every even number
    for (int i=4; i<mx; i+=2){
      spf[i] = 2;
    }
    
    for (int i=3; i*i<mx; i++)
    {
        if (spf[i] == i)
        {
            for (int j=i*i; j<mx; j+=i){
                if (spf[j]==j)
                    spf[j] = i;
            }
        }
    }
}

vector<int> getFactorization(int x)
{
    vector<int> ret;
    while (x != 1)
    {
        ret.push_back(spf[x]);
        x = x / spf[x];
    }
    return ret;
}

int main()
{
    sieve();
    int x;
    cin >> x;
    cout << "prime factorization for " <<x<<" : ";

    vector <int> p = getFactorization(x);

    for (int i=0; i<p.size(); i++) {
        cout << p[i] << " ";
    }
    cout << "\n";
    return 0;
}

সিভ এর মাধ্যমে প্রাইম ফ্যাক্টরাইজেশন বের করা-

method-01:

#include<bits/stdc++.h>
using namespace std;
#define MAX 1000005

int prime[MAX];
vector<int> p;

void sieve()
{
    memset(prime,0, sizeof(prime));

    prime[0]=prime[1]=1;

    for(int i=4; i<MAX; i+=2){
        prime[i]=1;
    }

    for(int i = 3; i*i < MAX; i+=2)
    {
        if(prime[i]==0)
        {
            for(int j = i*i; j < MAX; j+=i)
            prime[j]=1;
        }
    }
    for(int i = 2; i < MAX; i++)
        if(prime[i]==0)
            p.push_back(i);

}
int prime_factorize(int n)
{
    for(int i=0; i<p.size(); i++)
    {
        while(n%p[i]==0)
        {
            n/=p[i];
            cout << p[i] << "\n";
        }
        if(n==1)
            break;
    }
    if(n!=1)
        cout << "\n";
}
int main ()
{
    sieve();
    int n;
    cin >> n;
    prime_factorize(n);
    return 0;
}

method-02:

#include<bits/stdc++.h>
using namespace std;
const int mx = 1000005;
int prime[mx];
vector<int> p, prime_factor;

void seive()
{
    memset(prime, 0, sizeof(prime));
    
    prime[0]=prime[1]=1;
    for(int i=4; i<mx; i+=2)
        prime[i]=1;

    for(int i=3; i*i<mx; i+=2){
        if(prime[i]==0){
            for(int j=i*i; j<mx; j+=i)
                prime[j]=1;
        }
    }
    for(int i=2; i<mx; i++){
        if(prime[i]==0){
            p.push_back(i);
        }
    }
}
void primeFactorization(int x)
{
    for(int i=0; i<p.size(); i++){
        while(x % p[i] == 0){
            x/=p[i];
            prime_factor.push_back(p[i]);
        }
        if(x==1) break;
    }
    if(x != 1)prime_factor.push_back(x);
}

int main()
{
    seive();
    int n;
    cin >> n;
    primeFactorization(n);
    for(int i=0; i<prime_factor.size(); i++)
        cout << prime_factor[i] << " ";
    return 0;
}

আরেকটটি ইফিশেয়েন্ট প্রাইম ফ্যাক্টরাইজেশন এর কোড দেওয়া হল

প্রাইম ফ্যাক্টরাইজেশন বের করতে হলে প্রাইম নাম্বার দিয়ে চেক করতে হবে এটি  Divisible  কিনা। এখন প্রাইম নাম্বার গুলো হল 2, 3, 5, 7....  নরমালি যদি আমরা  Divisible কিনা তার জন্য প্রথমে চেক করি 2 দিয়ে কারন 2 হচ্ছে প্রাইম নাম্বার মধ্যে একদম ছোট।

#include "bits/stdc++.h"
using namespace std;

int smallestfactor(int n, int start=2)
{
    int test=start;
    int maxtest = sqrt(n);

    while(test<=maxtest)
    {
        if(n%test==0){
            return test;
        }
        test++;
    }
    return n;
}
vector<int>factors(int n)
{
    vector<int>factorlist;
    int p=2;
    while(n!=1)
    {
        p=smallestfactor(n, p);
        factorlist.push_back(p);
        n/=p;
    }
    return factorlist;
}
void writeFactors(int n, vector<int>f)
{
    cout<<"Prime factorisation: "<<f[0]<<" ";
    for (int i=1; i<f.size(); i++){
        cout << f[i] << " ";
    }

    int cur = f[0];
    cout << "\nprime_factorization is : " << cur << " , ";
    for(int i=1; i<f.size(); i++)
    {
        if(f[i]!=cur){
            cout << f[i] << " ";
        }
        cur=f[i];
    }
}
int main ()
{
    int n;
    cout << "Input n: ";
    cin >> n;

    vector<int>f=factors(n);
    writeFactors(n, f);
}