Modular Exponentation

Modular Exponentation digunakan untuk menemukan nilai sisa pembagian.

Ada 3 cara untuk melakukan modular exponentation, yaitu: Straightforward Method, Memory Efficient Method, dan Bit Shift Method.

1. Straightforward Method

Berikut kode untuk metode straightforward.

#include <stdio.h>

int ModEx1(int a, int b, int c)
{   int i, res = a;

    for(i = b; i > 0; i--) res *= a;

    return res % c;
}

int main()
{   int a, b, c;
    scanf("%d %d %d", &a, &b, &c);

    printf("%d\n", ModEx1(a, b, c));
}

2. Memory Efficient Method

3. Bit Shift Method

Convert Int to String

Kadang kala kita harus mengubah suatu tipe data menjadi tipe data lain dengan isi yang sama. Misalnya, kita ingin mengubah tipe data int menjadi string. Untuk mengubah tipe data menjadi string (char*), kita bisa menggunakan perintah ini.

sprintf(char *dest, const char *Format, ...);

Catatan
Perintah tersebut hanya bisa digunakan untuk mengubah tipe data lain menjadi string (char*) saja dan tidak bisa sebaliknya. Misalnya, tidak bisa dari string (char*) menjadi int.

Berikut contoh implemetasinya.

#include <stdio.h>

int main()
{
    char string[10];
    int number = 10341;
  
    sprintf(string, "%d", number);
  
    printf("%s\n", string);
}

Berikut contoh kode untuk mengubah tipe data long long int menjadi string.

#include <stdio.h>

int main()
{
    char string[10];
    long long int number = 41798654817561947;
   
    sprintf(string, "%lld", number);
   
    printf("%s\n", string);
}

Mengecek Bilangan Prima

Bilangan prima adalah bilangan yang habis dibagi oleh 1 dan bilangan itu sendiri.

Ada banyak cara untuk mengecek apakah suatu bilangan prima atau bukan. Berikut ini merupakan algoritma yang sering kita jumpai.
1. Bilangan x dibagi 2, 3, 4, ..., sampai x/2

Kekurangan dari algoritma di atas ialah prosesnya sangat lambat dan tidak efektif untuk bilangan yang besar.

Solusinya, gunakan algortima berikut ini.
1. Bilangan x dicek apakah kurang dari 2 atau merupakan bilangan kelipatan 2.
2. Jika ya, maka bukan bilangan prima.
3. Jika tidak, maka bilangan x dibagi 3, 5, 7, ..., sampai akar dari x.

Algoritma ini sangat efektif untuk mengecek bilangan yang sangat besar. Misalnya, 2147483647. Bilangan tersebut merupakan batas atas dalam variabel signed integer. Untuk mengecek bilangan tersebut, biasanya program membutuhkan waktu beberapa detik. Namun, jika menggunakan algoritma ini, pengecekan bisa selesai dalam seketika.

Berikut implementasinya dalam bahasa C.

// Cek Bilangan Prima
#include<stdio.h>
#include<math.h>

int main()
{    int N, akar, i;
    scanf("%d", &N);

    if(N < 2 || N % 2 == 0)
    {    printf("Bukan bilangan prima");
        return 0;
    }

    akar = sqrt(N);
    for(i = 3; i <= akar; i+=2)
        if(N % i == 0)
        {    printf("Bukan bilangan prima");
            return 0;
        }
       
    printf("Bilangan prima");
}

Contoh input:
2147483647

Output:
Bilangan prima

Greatest Common Divisor

Greatest Common Divisor (GCD) adalah faktor persekutuan terbesar (FPB) dalam bahasa Indonesia.

Berikut implementasinya dalam bahasa C.

// Greatest Common Divisor (GCD)
#include<stdio.h>

int gcd(int m, int n)
{  
    if(n == 0) return m;
    return gcd(n, m%n);
}

int main()
{  
    int m, n;
    printf("Masukkan 2 angka dipisah spasi: ");
    scanf("%d %d", &m, &n);
  
    printf("FPB: %d\n", gcd(m, n));
}

Contoh Input:
15 9

Output:
3