Asal Sayı Problemi

Bilgisayarımdaki arşivden çıkan bir başka soru ile karşınızdayım. Soru metni elimde yok ama hafızam beni yanıltmıyorsa aşağıdaki gibiydi. Alice ve Bob kendi aralarında bir oyun icat ediyorlar. İki arkadaş 1..10^9 arasındaki bazı asal sayıları bulmak istiyorlar.

Alice: sadece 1,3,5 rakamlarından oluşan asal sayıları sayıyor. Diğer değişle sayının tüm basamakları 1,3,5 rakamından biri olmak zorunda. Bob: sadece 5,7,9 rakamlarından oluşan asal sayıları sayıyor.

İkisi de işlemlerini bitirince buldukları asal sayı miktarını karşılaştırıyor. Kim daha fazla asal sayı bulursa o kazanıyor.

Beklenen girdi: yok. Beklenen çıktı: kim kazandıysa onun adını basıyoruz (Alice veya Bob)

Çözüm

Problemdeki input single pass için çok büyük. Dolayısı ile daha iyi bir çözüme ihtiyacımız var. Sadece 1, 3 ve 5 rakamlarından oluşan tüm tam sayıları bulalım.

Bunun için ağacımsı bir yapı kullanabiliriz ki bize O(2^n) gibi bir karmaşıklık verir. n çok büyük olmadığı için kolayca hesaplayabiliriz.

Basamak sayısı 3 olduğu için perfectly balanced ternary tree oluşturduğumuzda elimizde (3^10 - 1) / 2 = 29524 tane değer olur. Bu sayıları depolamak gibi bir derdimiz yok geldiği gibi işleyebiliriz. Asallık testi için klasik O(sqrt(n)) kompleksitesine sahip bir algoritma kullanırsak tamamız.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

#include <bits/stdc++.h>
using namespace std;

int r = 0; // result

// primality check
bool isPrime(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0)
        return false;
    
    for (int i = 5; i * i <= n; i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
    return true;
}

// Perfectly balanced ternary tree recursion
void primes(vector<int>& rr, int val , int level) {
    if (level == 10) return;
    r+=isPrime(val);
    for (int i = 0; i < rr.size(); i++)
        primes(rr, val * 10 + rr[i], level + 1);
}

int main() {
    vector<int> s = {1,3,5};
    vector<int> t = {5,7,9};

    primes(s, 1, 0);
    r*=-1;
    primes(t, 1, 0);

    if(r > 0) cout << "Alice";
    else cout << "Bob";

    return 0;
}