Category Archives: Number Theory

Algorithm: Euler’s GCD

Posted on June 3, 2017 | Leave a comment

https://www.youtube.com/watch?v=WAyPIMme3Yw&index=8&list=PL2_aWCzGMAwLL-mEB4ef20f3iqWMGWa25
code:

int euclid_gcd(int a,int b)
{
    int dividend,divisor,remainder;
    dividend = a>=b?a:b;
    divisor= a<=b?a:b;

    while(divisor!=0)
    {
        remainder=dividend%divisor;
        dividend=divisor;
        divisor=remainder;
    }
    return dividend;
}

int euclid_gcd(int a,int b)

{

int dividend,divisor,remainder;

dividend = a>=b?a:b;

divisor= a<=b?a:b;

while(divisor!=0)

{

remainder=dividend%divisor;

dividend=divisor;

divisor=remainder;

}

return dividend;

}

more optimized:

int euclid_gcd(int a,int b)
{
    int dividend,divisor,remainder;
    dividend = a;
    divisor= b;

    while(divisor!=0)
    {
        remainder=dividend%divisor;
        dividend=divisor;
        divisor=remainder;
    }
    return dividend;
}

int euclid_gcd(int a,int b)

{

int dividend,divisor,remainder;

dividend = a;

divisor= b;

while(divisor!=0)

{

remainder=dividend%divisor;

dividend=divisor;

divisor=remainder;

}

return dividend;

}

Recursive:

#include<bits/stdc++.h>
int euclid_gcd_recursive(int a,int b)
{
    return b==0?a:euclid_gcd_recursive(b,a%b);
}
int main()
{
    int d,x,z;
    printf("Scanf a and b:");
    scanf("%d %d",&x,&z);
    d=euclid_gcd_recursive(x,z);
    printf("GCD= %d",d);
    return 0;
}

#include<bits/stdc++.h>

int euclid_gcd_recursive(int a,int b)

{

return b==0?a:euclid_gcd_recursive(b,a%b);

}

int main()

{

int d,x,z;

printf("Scanf a and b:");

scanf("%d %d",&x,&z);

d=euclid_gcd_recursive(x,z);

printf("GCD= %d",d);

return 0;

}

http://www.progkriya.org/gyan/basic-number-theory.html#section3

Leave a comment

Posted in A ll Codes, Algorithm, C, Euler GCD, Number Theory

Algo: Prime factorization of a number

Posted on June 3, 2017 | Leave a comment

https://www.youtube.com/watch?v=6PDtgHhpCHo&index=6&list=PL2_aWCzGMAwLL-mEB4ef20f3iqWMGWa25

code:

#include<bits/stdc++.h>
int main()
{
    int i,n,ct=0;;
    scanf("%d",&n);
    for(i=2;i<=sqrt(n);i++)
    {
        if(n%i==0)
        {
            ct=0;

            while(n%i==0)
            {
                n=n/i;
                ct++;
            }
            printf("(%d^%d)X",i,ct);
        }

    }
    if(n!=1)
        printf("%d^%d",n,1); //it's cleared but will see more about this in future

    return 0;
}

#include<bits/stdc++.h>

int main()

{

int i,n,ct=0;;

scanf("%d",&n);

for(i=2;i<=sqrt(n);i++)

{

if(n%i==0)

{

ct=0;

while(n%i==0)

{

n=n/i;

ct++;

}

printf("(%d^%d)X",i,ct);

}

if(n!=1)

printf("%d^%d",n,1); //it's cleared but will see more about this in future

return 0;

}

I/O:

input: 36
output: (2^2)X(3^2)X

1 2	input: 36 output: (2^2)X(3^2)X

Leave a comment

Posted in A ll Codes, Algorithm, C, Prime factorization

Prime Number: Trial division | Prime check upto N in C

Posted on June 2, 2017 | Leave a comment

https://www.youtube.com/watch?v=7VPA-HjjUmU

code:

#include<bits/stdc++.h>

int main()
{
    int i,j,n,flag=0;
    printf("enter number: ");
    scanf("%d",&n);
    for(i=2;i<=n;i++) //first iterate upto n
    {
        flag=1;
        for(j=2;j<=sqrt(i);j++) //trial division is using here //(i/2) can also use instead of sqrt(i)
        {
            if(i%j==0)
            {
                flag=0;
                break;
            }
        }
        if(flag==1)
        {
            printf("%d \t",i);
        }
    }


return 0;

}

#include<bits/stdc++.h>

int main()

{

int i,j,n,flag=0;

printf("enter number: ");

scanf("%d",&n);

for(i=2;i<=n;i++) //first iterate upto n

{

flag=1;

for(j=2;j<=sqrt(i);j++) //trial division is using here //(i/2) can also use instead of sqrt(i)

{

if(i%j==0)

{

flag=0;

break;

}

if(flag==1)

{

printf("%d \t",i);

}

return 0;

}

Help can be find:
http://www.studystreet.com/c-program-print-prime-numbers/
http://www.codingalpha.com/prime-number-c-program/
https://en.wikipedia.org/wiki/Primality_test

Leave a comment

Posted in A ll Codes, Algorithm, C, Trial Division

Tagged Trial Divison

Prime Finding: Sieve of Erastosthenes

Posted on June 2, 2017 | Leave a comment

I have watched the videos from mycodeschool and implemented it:
code:

//find all prime numbers upto n
//sieve of erastosthenes

#include<bits/stdc++.h>
int main()
{
    int n;
    scanf("%d",&n);
    int primes[n];
    for(int i=0; i<=n; i++)
    {
        primes[i]=1; //make prime to all numbers between 0 and n
    }
    primes[0]=0; //0 not prime
    primes[1]=0; //1 not prime
    for(int i=2; i<=n; i++) //2 to n iterating
    {
        if(primes[i]==1)   //if 2 to n is prime then
        {
            for(int j=2; i*j<=n; j++) //j=2 and i*j<=9 means 2*2<=9  
            {
                primes[i*j]=0;  //primes[i*j=2*2=4] means primes[4]=0;
            }
            printf("%d ",i); //
        }
    }

}

//find all prime numbers upto n

//sieve of erastosthenes

#include<bits/stdc++.h>

int main()

{

int n;

scanf("%d",&n);

int primes[n];

for(int i=0; i<=n; i++)

{

primes[i]=1; //make prime to all numbers between 0 and n

}

primes[0]=0; //0 not prime

primes[1]=0; //1 not prime

for(int i=2; i<=n; i++) //2 to n iterating

{

if(primes[i]==1) //if 2 to n is prime then

{

for(int j=2; i*j<=n; j++) //j=2 and i*j<=9 means 2*2<=9

{

primes[i*j]=0; //primes[i*j=2*2=4] means primes[4]=0;

}

printf("%d ",i); //

}

Video:

https://www.youtube.com/watch?v=eKp56OLhoQs&index=4&list=PL2_aWCzGMAwLL-mEB4ef20f3iqWMGWa25

Leave a comment

Posted in Algorithm, Sieve of Erastosthenes

Tagged Erastosthenes, Prime, Sieve

LCM – Least Common Multiple

Posted on November 1, 2015 | Leave a comment

Multiple of 3 is
3×1=3
3×2=6
3×3=9
3×4=12
3×5=15
3×6=18
3×7=21
3×8=24
3×9=27
3×10=30

Multiple of 4 is
4×1=4
4×2=8
4×3=12
4×4=16
4×5=20
4×6=24
4×7=28
4×8=32
4×9=36
4×10=40

Here in 3 and 4 mutilples common is 12
and it is only one value and so it is the lowest also then but if there were some more values than result could be something changed.

So here LCM=12
Here I implemented the code
applied this formula
$lcm (a, b) = \frac{a \cdot b}{\gcd (a, b)};$

code goes here :

#include<stdio.h>
 int main()
{
    int a,b,x,gcd,lcm;
    scanf("%d %d",&a,&b);

    if(a<b)//it is not possible for gcd to be greater than the lowest value
    {
        x=a;
    }
    else
    {
        x=b;
    }
    for( ;x>=1;x--){ //here i haven't initialized the value of x as x is first at outside
        if(a%x==0 && b%x==0){
            gcd=x;
            break; //here i have used break as if it is not here then when the division will happen it will run the loop till 1 so answer will be always 1
        }
    }

printf("GCD is %d\n",gcd);
lcm=a*b/gcd;
printf("LCM is %d\n",lcm);

    return 0;
}

#include<stdio.h>

int main()

{

int a,b,x,gcd,lcm;

scanf("%d %d",&a,&b);

if(a<b)//it is not possible for gcd to be greater than the lowest value

{

x=a;

}

else

{

x=b;

}

for( ;x>=1;x--){ //here i haven't initialized the value of x as x is first at outside

if(a%x==0 && b%x==0){

gcd=x;

break; //here i have used break as if it is not here then when the division will happen it will run the loop till 1 so answer will be always 1

}

printf("GCD is %d\n",gcd);

lcm=a*b/gcd;

printf("LCM is %d\n",lcm);

return 0;

}

Leave a comment

Posted in ACM-ICPC, LCM, Mathematics

Tagged LCM - Least Common Multiple

GCD Greatest Common Divisor(Factor)/Highest Common Factor

Posted on November 1, 2015 | Leave a comment

এখানে লজিকটা হচ্ছে…Here the logic is:
For 12:
1×12=12
2×6=12
3×4=12
So factor of 12=1,2,3,4,6,12
(We don’t need the negative values here)

For 30:
1×30=30
2×15=30
3×10=30
5×6=30
So factor of 30=1,2,3,5,6,10,15,30

Now which is the common factor among 12 and 30
So factor of 12=1,2,3,4,6,12
So factor of 30=1,2,3,5,6,10,15,30

common factor=1,2,3,6
Largest common factor here=6

So now if we divide 12/6 then we get 2
and for 30/6 we get 5

that is all divided perfectly so the logic should be like this

1.Find all the factors of each number
2. Circle the common factors
3. Choose the greatest of those
4. Divide the existing number with greatest common factor thern also get a perfect divide

Here is my code:

#include<stdio.h>
 int main()
{
    int a,b,x,gcd;
    scanf("%d %d",&a,&b);

    if(a<b)//it is not possible for gcd to be greater than the lowest value
    {
        x=a;
    }
    else
    {
        x=b;
    }
    for( ;x>=1;x--){ //here i haven't initialized the value of x as x is first at outside
        if(a%x==0 && b%x==0){
            gcd=x;
            break; //here i have used break as if it is not here then when the division will happen it will run the loop till 1 so answer will be always 1
        }
    }

printf("GCD is %d\n",gcd);

    return 0;
}

#include<stdio.h>

int main()

{

int a,b,x,gcd;

scanf("%d %d",&a,&b);

if(a<b)//it is not possible for gcd to be greater than the lowest value

{

x=a;

}

else

{

x=b;

}

for( ;x>=1;x--){ //here i haven't initialized the value of x as x is first at outside

if(a%x==0 && b%x==0){

gcd=x;

break; //here i have used break as if it is not here then when the division will happen it will run the loop till 1 so answer will be always 1

}

printf("GCD is %d\n",gcd);

return 0;

}

Here is a link that described many thinks about this clearly: http://www.mathsisfun.com/greatest-common-factor.html

Another method can also apply here:
link for understanding the modarithmetic euclidean algorithmhttps://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/the-euclidean-algorithm

Code:

#include<stdio.h>

int main()
{

    int a,b,t,x,gcd;
    scanf("%d %d",&a,&b);
    if(a==0)
        gcd=a;
    else if(b==0)
        gcd=b;
    else
    {
        while(b!=0)
        {

            t=b;
            b=a%b;
            a=t;
        }
        gcd=a;
    }
    printf("GCD is %d\n",gcd);

    return 0;
}

#include<stdio.h>

int main()

{

int a,b,t,x,gcd;

scanf("%d %d",&a,&b);

if(a==0)

gcd=a;

else if(b==0)

gcd=b;

else

{

while(b!=0)

{

t=b;

b=a%b;

a=t;

}

gcd=a;

}

printf("GCD is %d\n",gcd);

return 0;

}

Leave a comment

Posted in ACM-ICPC, GCD, Mathematics

Tagged GCD Greatest Common Divisor(Factor)/Highest Common Factor

Category Archives: Number Theory

Algorithm: Euler’s GCD

Algo: Prime factorization of a number

Prime Number: Trial division | Prime check upto N in C

Prime Finding: Sieve of Erastosthenes

LCM – Least Common Multiple

GCD Greatest Common Divisor(Factor)/Highest Common Factor

Caution and Tips:

About Me & MyBlog

Recent Comments

Categories

My Facebook

Recent Posts

Archives

Category Archives: Number Theory

Algorithm: Euler’s GCD

Algo: Prime factorization of a number

Prime Number: Trial division | Prime check upto N in C

Prime Finding: Sieve of Erastosthenes

LCM – Least Common Multiple

GCD Greatest Common Divisor(Factor)/Highest Common Factor

Caution and Tips:

About Me & MyBlog

Recent Comments

Categories

My Facebook

Recent Posts

Tags

Archives