Category Archives: Number Theory

Algorithm: Euler’s GCD

Posted on June 3, 2017 | Leave a comment

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

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

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:

Leave a comment

Posted in Algorithm, Sieve of Erastosthenes

Tagged Erastosthenes, Prime, Sieve

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

Caution and Tips:

About Me & MyBlog

Category

Recent Posts

Recent Comments

My Facebook

Follow Me

My Algorithmic Progress in OJ’s

My Github

My Linkedin

Count per Day

Archives

This site is powered by:

Bookmarks

My Coding Page

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

Caution and Tips:

About Me & MyBlog

Category

Recent Posts

Recent Comments

My Facebook

Follow Me

My Algorithmic Progress in OJ’s

My Github

My Linkedin

Tags

Count per Day

Archives

This site is powered by:

Bookmarks

My Coding Page