# 🎈 Asal Sayı Hesaplama (Prime)

📜 Açıklama
👶 Basit
✨ Optimize
✅ Test
📜 Açıklama

The first optimization takes advantage of the fact that two is the only even prime. Thus we can check if a number is even and as long as its greater than 2, we know that it is not prime.

Our second optimization takes advantage of the fact that when checking factors, we only need to check odd factors up to the square root of a number. Consider a number $n$ decomposed into factors $n=ab$ . There are two cases, either $n$ is prime and without loss of generality, $a=n, b=1$ or $n$ is not prime and $a,b \neq n,1$ . In this case, if $a > \sqrt{n}$ , then $b<\sqrt{n}$ . So we only need to check all possible values of $b$ and we get the values of $a$ for free! This means that even the simple method of checking factors will increase in complexity as a square root compared to the size of the number instead of linearly.

👶 Basit
def is_prime(number):    if number < 2:        return False​    for i in range(2, number):        if number % i == 0:            return False​    return True
✨ Optimize
import mathdef is_prime_fast(number):    if number < 2:        return False​    root = round(math.sqrt(number))    for i in range(2, root + 1):        if number % i == 0:            return False​    return True
✅ Test
# Doğruluğu test etmefor n in range(10000):    assert is_prime(n) == is_prime_fast(n)​# Hız testleri# %%timeit ile hesaplanmıştır (jupyter notebook)is_prime(67867967) # 4.85 s ± 94.8 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)is_prime_fast(67867967) # 578 µs ± 12.4 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

# 🔢 Mersenne Number

📜 Açıklama
👨‍💻 Kod
📜 Açıklama

A Mersenne number is any number that can be written as $2^p - 1$ for some $p$ . For example, 3 is a Mersenne number ( $2^2 - 1$ ) as is 31 ( $2^5 - 1$ ). We will see later on that it is easy to test if Mersenne numbers are prime.

👨‍💻 Kod
def mersenne_number(p):    return 2 ** p - 1​def is_prime(number):    if number < 2:        return False​    for i in range(2, number):        if number % i == 0:            return False​    return True​def get_primes(n_start, n_end):    return [x for x in range(n_start, n_end + 1) if is_prime(x)]​mersennes = [mersenne_number(x) for x in get_primes(3, 65)]

# 🪁 Lucas Lehmer

📜 Açıklama
👨‍💻 Kod
📜 Açıklama

We can test if a Mersenne number is prime using the Lucas-Lehmer test. First let's write a function that generates the sequence used in the test. Given a Mersenne number with exponent $p$ , the sequence can be defined as

$n_0 = 4$ $n_i = (n_{i-1}^2 - 2) mod (2^p - 1)$

👨‍💻 Kod
def lucas_lehmer(p):    n = [4]​    limit = p - 2    mersenne = mersenne_number(p)​    for i in range(1, limit + 1):        n.append((n[i - 1] ** 2 - 2) % mersenne)​​    return n​ll_result = lucas_lehmer(17)

# 🔢 Mersenne Prime

📜 Açıklama
👨‍💻 Kod
📜 Açıklama

For a given Mersenne number with exponent $p$ , the number is prime if the Lucas-Lehmer series is 0 at position $p-2$ . Write a function that tests if a Mersenne number with exponent $p$ is prime. Test if the Mersenne numbers with prime $p$ between 3 and 65 (i.e. 3, 5, 7, ..., 61) are prime. Your final answer should be a list of tuples consisting of (Mersenne exponent, 0) (or 1) for each Mersenne number you test, where 0 and 1 are replacements for False and True respectively.

👨‍💻 Kod
def ll_prime(p):    ll = lucas_lehmer(p)    return not bool(ll[-1])​mersenne_primes = [(x, int(ll_prime(x))) for x in get_primes(3, 65)]

# 💯 Sieve of Eratosthenes

📜 Açıklama
👨‍💻 Kod
📜 Açıklama

The method works as follows (see here for more details)

1. Generate a list of all numbers between 0 and N; mark the numbers 0 and 1 to be not prime

2. Starting with $p=2$ (the first prime) mark all numbers of the form $np$ where $n>1$ and $np <= N$ to be not prime (they can't be prime since they are multiples of 2!)

3. Find the smallest number greater than $p$ which is not marked and set that equal to $p$, then go back to step 2. Stop if there is no unmarked number greater than $p$ and less than $N+1$

We will break this up into a few functions, our general strategy will be to use a Python list as our container although we could use other data structures. The index of this list will represent numbers.

We have implemented a sieve function which will find all the prime numbers up to $n$. You will need to implement the functions which it calls. They are as follows

• list_true Make a list of true values of length $n+1$ where the first two values are false (this corresponds with step 1 of the algorithm above)

• mark_false takes a list of booleans and a number $p$. Mark all elements $2p,3p,...n$ false (this corresponds with step 2 of the algorithm above)

• find_next Find the smallest True element in a list which is greater than some $p$ (has index greater than $p$ (this corresponds with step 3 of the algorithm above)

• prime_from_list Return indices of True values

Remember that python lists are zero indexed. We have provided assertions below to help you assess whether your functions are functioning properly.

👨‍💻 Kod
def list_true(n):    return [False] * (2) + [True] * (n - 1)​# Test# assert len(list_true(20)) == 21# assert list_true(20)[0] is False# assert list_true(20)[1] is False​def mark_false(bool_list, p):    limit = ((len(bool_list) -1)  // p) + 1    for i in range(2, limit):        bool_list[i*p] = False    return bool_list​# Test# assert mark_false(list_true(6), 2) == [False, False, True, # True, False, True, False]​def find_next(bool_list, p):    for i in range(p + 1, len(bool_list)):        if bool_list[i]:            return i# Test# assert find_next([True, True, True, True], 2) == 3# assert find_next([True, True, True, False], 2) is None​def prime_from_list(bool_list):    return [i for i, x in enumerate(bool_list) if x]​# Test# assert prime_from_list([False, False, True, True, False]) ==  [2, 3]​def sieve(n):    bool_list = list_true(n)    p = 2    while p is not None:        bool_list = mark_false(bool_list, p)        p = find_next(bool_list, p)    return prime_from_list(bool_list)​assert sieve(1000) == get_primes(0, 1000)​# Hız testleri# %%timeit ile hesaplanmıştır (jupyter notebook)sieve(1000) get_primes(0, 1000)​# 402 µs ± 7.47 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)# 4.9 ms ± 93.2 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

# 👨‍💻 Code Snippets

📋 List İşlemleri
🍒 Verileri Sınıflara Göre Gruplama
📊 İstatistik
📙 Dict
📋 List İşlemleri
[x for x in iter if x = 1]
sum([obj["items"] for obj in groups[name]]
[(name, sum([obj["items"] for obj in groups[name]])) for name in groups]
lis = [("a",1) ...]max(lis, key=lambda x:x[1]) # 2. elemana göre hesaplama
🍒 Verileri Sınıflara Göre Gruplama
def group_by_field(data, fields):​    def generate_keys(data, field):        yield set([x[field] for x in data])​    groups = {}    for field in fields:        group = {name: [] for name in generate_keys(data, field)}        groups[field] = group​    for x in data:        groups[field][x[field]].append(data)​    return groups
📊 İstatistik
import mathimport statistics​def grap_data(scripts, key):    return [script[key] for script in scripts]​def standart_deviation(datas, avg):    nominator = 0    for data in datas:        nominator += (data - avg) ** 2​    return math.sqrt(nominator / len(datas))​def median(datas, quartile = 2):    center = len(datas) // 2​    if quartile == 1:        center = center // 2    if quartile == 3:        center += center // 2​    datas = sorted(datas)​    if len(datas) % 2 == 0:        med = (datas[center - 1] + datas[center]) / 2    else:        med = datas[center]​    return med​def describe(key):​    datas = grap_data(scripts, key)​    total = sum(datas)    avg = total / len(datas)    s = standart_deviation(datas, avg)​    med = median(datas)    q25 = median(datas, 1)    q75 = median(datas, 3)​    return (total, avg, s, q25, med, q75)
📙 Dict
for field in groups:    # print(field)    for name in groups[field]:        # print(name)        for data in groups[field][name]:            print(data)            break        break    break

# 📂 Yüksek Miktarda Veriyi Ele Alma

🧩 Format
✨ Verilerin İşlenmesi
🧩 Format
{    field: {        name : [ # Be careful it's list (not dict)            data: {                "items": 5 # some value            },            ...        ],        ...    },    ...}
✨ Verilerin İşlenmesi
def group_by_field(data, fields):​    def create_keys(data, field):        return set([x[field] for x in data])​    groups = {}    for field in fields:        group = {name: [] for name in create_keys(data, field)}        groups[field] = group​    for x in data:        groups[field][x[field]].append(x)​    return groups​def get_max_item(groups, attribute):    max_items = []    for group in groups:        field = groups[group]​        sums = []        for name in field:            sums.append((name, sum([data[attribute] for data in field[name]])))​        max_items.append(max(sums, key=lambda x:x[1]))​    return max_items