মৌলিক উৎপাদকে বিশ্লেষণ (Prime Factorization)

একটি সংখ্যা n দেওয়া আছে। এটিকে মৌলিক উৎপাদকে বিশ্লেষণ করতে হবে।

/**Bismillahir Rahmanir Rahim.**/

#include <bits/stdc++.h>

using namespace std;

int ara[1000], x;

int primeFact(int n)
{
    while(n%2==0)
    {
        n/=2;
        ara[x++] = 2;
    }
    int limit = sqrt(n+1);
    for(int i=3; i<=limit && n>1; i+=2)
        while(n%i==0)
        {
            n/=i;
            ara[x++] = i;
        }
    if(n>2) ara[x++] = n;
    return x;
}
int main()
{
    int n=10000, till;

    till = primeFact(n);

    for(int i=0; i<till; i++)
        printf("%d ", ara[i]);
    return 0;
}

Read More

সেগমেন্টেড সীভ (Segmented Sieve)

দুইটি সংখ্যা A আর B দেওয়া আছে (A<B)। A থেকে B পর্যন্ত প্রাইম নাম্বার গুলো প্রিন্ট করতে হবে। A = 100, B = 1000 এর জন্য নিচের কোড করা হল।

/**Bismillahir Rahmanir Rahim.**/

#include <bits/stdc++.h>

using namespace std;

int prime[100], x, final_prime[100], y;

void seivePrime(char prime_b[], int b)
{
    prime_b[1]=1;
    int till = sqrt(b+1);
    for(int i=4; i<=till; i+=2)
        prime_b[i] = 1;
    int limit = sqrt(till)+1;
    for(int i=3; i<=limit; i+=2)
    {
        if(!prime_b[i])
        {
            for(int j=i*i; j<=till; j+=(i*2))
                prime_b[j] = 1;
        }
    }
    prime[0] = 2;
    for(int i=3; i<=till; i+=2)
        if(!prime_b[i])
            prime[++x] = i;
}

void segment_prime(int A, int B)
{
    if(A==1) A+=1;
    char segment[B-A+1];
    memset(segment, 0, sizeof(segment));
    for(int i=0; i<x; i++)
    {
        int start = prime[i]*prime[i];
        if(start<A) start = ((A+prime[i]-1)/prime[i])*prime[i];
        for(; start<=B; start += prime[i])
            segment[start-A] = 1;
    }
    if(A == 2) final_prime[y++] = 2;
    int j=A+1;
    if(A%2) j=A;
    for(; j<=B; j+=2)
        if(!segment[j-A])
            final_prime[y++] = j;
}
int main()
{
    int a = 100, b = 1000;
    char prime_b[123];
    memset(prime_b, 0, sizeof(prime_b));

    seivePrime(prime_b, b);

    segment_prime(a, b);

    for(int i=0; i<y; i++)
        printf("%d ", final_prime[i]);
    return 0;
}

Read More

সীভ মেথডে প্রাইম বের করা (Calculation Prime Number Using Sieve)

1 থেকে n পর্যন্ত সব প্রাইম নাম্বার বের করতে হবে সীভ মেথডে। নিচের প্রোগ্রামে ১০০০ পর্যন্ত বের করা হল।
Complexity : O(n log log n).

/**Bismillahir Rahmanir Rahim.**/

#include <bits/stdc++.h>

using namespace std;

void seivePrime(char seive[])
{
    seive[1]=1;
    int till=1000;
    for(int i=4; i<=till; i+=2)
        seive[i] = 1;
    int limit = sqrt(till)+1;
    for(int i=3; i<=limit; i+=2)
    {
        if(!seive[i])
            for(int j=i*i; j<=till; j+=(i*2))
                seive[j] = 1;
    }
}

int main()
{
    char seive[1005];
    memset(seive, 0, sizeof(seive));

    seivePrime(seive);

    for(int i=2; i<=1000; i++)
        if(!seive[i])
            printf("%d ", i);
    return 0;
}

Read More