🔢 Algoritma Örnekleri

🎈 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 nn decomposed into factors n=abn=ab . There are two cases, either nn is prime and without loss of generality, a=n,b=1a=n, b=1 or nn is not prime and a,bn,1a,b \neq n,1 . In this case, if a>na > \sqrt{n} , then b<nb<\sqrt{n} . So we only need to check all possible values of bb and we get the values of aa 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 math
def 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 etme
for 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 2p12^p - 1 for some pp . For example, 3 is a Mersenne number ( 2212^2 - 1 ) as is 31 ( 2512^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 pp , the sequence can be defined as

n0=4n_0 = 4 ni=(ni122)mod(2p1)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 pp , the number is prime if the Lucas-Lehmer series is 0 at position p2p-2 . Write a function that tests if a Mersenne number with exponent pp is prime. Test if the Mersenne numbers with prime pp 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 math
import 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