Last non-zero digit of factorial

To find the last non-zero digit of a factorial number, the idea is to remove the extra zeroes in every step multiplying the numbers and don't need to hold the whole big number, just a small digit numbers from the last non-zero digits.
Here goes the code-

#include<stdio.h>
int main()
{
    long long int ans;
        int num;
        scanf("%d",&num);
 
        ans=1;
        for(int i=2;i<=num;i++)
        {
                ans=ans*i;
 
                while(ans%10==0)
                {
                        ans/=10;
                }
                ans%=10000000;
        }
        printf("%lld\n",ans%10);
 
        return 0;
}

Trailing zero in factorial

Finding number of trailing zero in factorial-

#include <stdio.h>
int main()
{
	int n,total,deno;
        scanf("%d",&n);
		
	total=0;
	deno=5;
	while(deno<=n)
	{
		total+=n/deno;
		deno*=5;
	}
	printf("%d\n",total);

	return 0;
}

Sum of Divisors of a Number

Sum of divisors of a Number can be found by the following formula.

Now the code. Following function calculate sum of divisors of a number-

#define i64 long long

i64 power(i64 N,i64 P)
{
	i64 sum=1,i;
	
	if(P==0)return 1;
	else
	{
		for(i=1;i<=P;i++)
			sum=sum*N;
		return sum;
	}
}

i64 sumofdivisor(i64 n)
{
	i64 sum=1,i,count;
	i64 sq=(i64)sqrt(n);
	
	for(i=0;prime[i]<=sq;i++)
	{
		count=0;
		while(n%prime[i]==0)
		{
			count++;
			n/=prime[i];
		}
		sum*=(i64)(power(prime[i],count+1)-1)/(prime[i]-1);
	}
	if(n>1)
		sum*=(n+1);
	return sum;
}

Bitwise sieve

Here is an implementation of Bitwise sieve. For full explanation See this and this-

#define MAX 100000000//max num to prime
#define LMT 10000 //sqrt(MAX)

int flag[MAX/64];
int prime[100000000],total;

#define chkC(n) (flag[n>>6]&(1<<((n>>1)&31)))
#define setC(n) (flag[n>>6]|=(1<<((n>>1)&31)))

void sieve() 
{
	unsigned i,j,k;

	flag[0]|=0;
	for(i=3;i<LMT;i+=2)
		if(!chkC(i))
			for(j=i*i,k=i<<1;j<MAX;j+=k)
				setC(j);

	prime[(j=0)++] = 2;//prime starts from 0 position
	for(i=3;i<MAX;i+=2)
		if(!chkC(i))
		{
			prime[j++] = i;
			//printf("%d\n",primes[j-1]);
		}
	total = j-1;
}

Number of divisor

To find the number of divisors of a number, first calculate find by sieve and then try this-

int number_of_divisor(int num)
{
 int j,count,div=1;
 for(j=0;prime[j]<=sqrt(num);j++) //prime array holds the prime numbers
 {
  count=0;
  while(num%prime[j]==0)
  {
   count++;
   num/=prime[j];
  }
  div*=(count+1);
 }
 if(num>1)
  div<<=1;
 return div;
}

This function returns the number of divisors of the given number.

Number of digits in factorial

This program calculate how many digit in factorial of the number in given base
Anyone can just calculate number of digits in decimal, then b=10 always.

#include <stdio.h>
#include <math.h>
int main()
{
	int number,i,base,digit;
	double c,a=0;

	printf("Give the base and the number: ");
	scanf ("%d%d",&base,&number);

	c=log10(base);
	for (i=number;i>=1;i--) {

		a+=(log10(i))/c; 
	}
	digit=a+1;
	printf ("%d\n",digit);

	return 0;
}

Sieve of Eratosthenes (Prime Finding)

The most popular prime finding method aka Sieve of Eratosthenes.

#define MAX 35000
#define lim 200

bool a[MAX];
int prime[MAX];

void sieve()
{
	int i,j;
	a[0]=1;a[1]=1;          //1 denotes not prime

	for(i=3;i<=lim;i+=2)    //even numbers are exclusive
	{
		if(a[i]==0)     //0 denotes prime
		{
			for(j=i*i;j < MAX;j+=i)
				a[j]=1;
		}
	}

	prime[0]=2;
	j=1;
	for(i=3;i < MAX;i+=2)     //even numbers are exclusive
	{
		if(a[i]==0)
			prime[j++]=i;
	}
}

Negative Base Conversion

Though, First time it may be a surprising fact that, "NEGATIVE BASE!!!", But it really exists. :)
Here goes it.Click Here for details.

NegaTernary(-3) Base conversion python implementation:

def negaternary(i):
    digits = []
    while i != 0:
        i, remainder = divmod(i, -3)
        if remainder < 0:
            i, remainder = i + 1, remainder + 3
        digits.insert(0, str (remainder))
    return ''.join(digits)

And Here is NegaBinary(-2) Base conversion in C:

#include<stdio.h>
int main()
{
	char a[100];
	int num,temp;

	while(~scanf("%d",&num))
	{
	while(num!=0)
	{
		temp=num%(-2);
		num/=(-2);
        if(temp < 0)
		{
			num+=1;
			temp+=2;
		}
		printf("%d ",temp);
	}
	puts("");
	}

	return 0;
}

GCD (Greatest Common Divisor)

Here are 3 different code for GCD, But the main Idea is always same-

//iterative gcd
int gcd ( int a, int b )
{
  int c;
  while ( b != 0 ) {
     c = b; b = a%b;  a = c;
  }
  return b;
}


//bitwise gcd
int gcd(int a, int b)
{

//actually this code is same as the previous
while(b) 
		b ^= a ^= b ^= a %= b;  //b^=a^=b^=a means swap(a,b)

return a;
}


//recursive gcd
int g_c_d(int a,int b)
{
	if(b==0)
		return a;
	else 
		return g_c_d(b,a%b);
}

Here is another short version of gcd using ternary operators:

int gcd ( int a, int b ) {
	return b ? gcd ( b, a % b ) : a ;
} 

Any Base Conversion

C++ implementation of Any Base to Any Base Conversion.

#include <cstdio>
#include <vector>
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

#define all(x) x.begin(),x.end()

template<class t> inline t power(t num,t p)
{
    if(!p)    return 1;return (num*power(num,p-1));
}

bool islow(char ch){if(ch>='a' && ch<='z') return true; return false;}
bool isupp(char ch){if(ch>='A' && ch<='Z') return true; return false;}
bool isdig(char ch){if(ch>='0' && ch<='9') return true; return false;}

//any base to decimal conversion
int todec(string s,int base)
{
    int i,j,temp,len,sum=0;

    len=s.length()-1;
    for(i=0,j=len;i<=len;i++,j--)
    {
        char ch=s.at(i);
        if(isdig(ch))         temp=ch-'0';
        else if(islow(ch))    temp=10+ch-'a';
        else if(isupp(ch))    temp=10+ch-'A';

        sum+=(temp*(power(base,j)));
    }

    return sum;
}


//decimal to any base conversion
string tobase(int num,int base)
{
    int temp;
    string s;
    char ch;
    if(!num)    return "0"; //special '0' case handling

    while(num>0)
    {
        temp=num%base;
        num/=base;
        if(temp<=9) s+=(temp+'0');
        else        s+=((temp-10)+'A');
    }
    reverse(all(s));
    return s;
}

Binary to Decimal and Decimal to Binary conversion

Here is a short code for Binary to Decimal Conversion-

int to_dec(string str)
{
    int num=0,i;
    int mask=1;

    for(i=str.length()-1;i>=0;i--)
    {
        if(str.at(i)=='1')
            num|=mask;
        mask<<=1;
    }

        cout << num << endl;
    
    return num;
}

And a short code for Decimal to Binary Conversion-

string to_bin(int num)
{
    string str="";
    int mask=1;

    while(num)
    {
        if(num&mask)
            str="1"+str;
        else
            str="0"+str;

        num>>=1;
    }

    cout << str << endl;
    return str;
}

শুরুর কথা

আলাভোলার প্রোগ্রামিং ব্লগ যেমন আছে তেমনি থাকবে। ওখানে বিভিন্ন প্রোগ্রামিং আলোচনা, টিপস এবং বর্ণনামূলক ব্যাপার স্যাপারগুলো থাকবে।
আর এই ব্লগটা শুধুমাত্র 'কোড আর্কাইভ' হিসেবে ব্যবহার হবে। যাতে প্রয়োজনের সময় এই কোডগুলো কাজে লাগানো যায়।