TheAlgorithms-Python

1
"""
2
Created on Thu Oct  5 16:44:23 2017
3

4
@author: Christian Bender
5

6
This Python library contains some useful functions to deal with
7
prime numbers and whole numbers.
8

9
Overview:
10

11
is_prime(number)
12
sieve_er(N)
13
get_prime_numbers(N)
14
prime_factorization(number)
15
greatest_prime_factor(number)
16
smallest_prime_factor(number)
17
get_prime(n)
18
get_primes_between(pNumber1, pNumber2)
19

20
----
21

22
is_even(number)
23
is_odd(number)
24
kg_v(number1, number2)  // least common multiple
25
get_divisors(number)    // all divisors of 'number' inclusive 1, number
26
is_perfect_number(number)
27

28
NEW-FUNCTIONS
29

30
simplify_fraction(numerator, denominator)
31
factorial (n) // n!
32
fib (n) // calculate the n-th fibonacci term.
33

34
-----
35

36
goldbach(number)  // Goldbach's assumption
37

38
"""
39

40
from math import sqrt
41

42
from maths.greatest_common_divisor import gcd_by_iterative
43

44

45
def is_prime(number: int) -> bool:
46
    """
47
    input: positive integer 'number'
48
    returns true if 'number' is prime otherwise false.
49

50
    >>> is_prime(3)
51
    True
52
    >>> is_prime(10)
53
    False
54
    >>> is_prime(97)
55
    True
56
    >>> is_prime(9991)
57
    False
58
    >>> is_prime(-1)
59
    Traceback (most recent call last):
60
        ...
61
    AssertionError: 'number' must been an int and positive
62
    >>> is_prime("test")
63
    Traceback (most recent call last):
64
        ...
65
    AssertionError: 'number' must been an int and positive
66
    """
67

68
    # precondition
69
    assert isinstance(number, int) and (
70
        number >= 0
71
    ), "'number' must been an int and positive"
72

73
    status = True
74

75
    # 0 and 1 are none primes.
76
    if number <= 1:
77
        status = False
78

79
    for divisor in range(2, int(round(sqrt(number))) + 1):
80
        # if 'number' divisible by 'divisor' then sets 'status'
81
        # of false and break up the loop.
82
        if number % divisor == 0:
83
            status = False
84
            break
85

86
    # precondition
87
    assert isinstance(status, bool), "'status' must been from type bool"
88

89
    return status
90

91

92
# ------------------------------------------
93

94

95
def sieve_er(n):
96
    """
97
    input: positive integer 'N' > 2
98
    returns a list of prime numbers from 2 up to N.
99

100
    This function implements the algorithm called
101
    sieve of erathostenes.
102

103
    >>> sieve_er(8)
104
    [2, 3, 5, 7]
105
    >>> sieve_er(-1)
106
    Traceback (most recent call last):
107
        ...
108
    AssertionError: 'N' must been an int and > 2
109
    >>> sieve_er("test")
110
    Traceback (most recent call last):
111
        ...
112
    AssertionError: 'N' must been an int and > 2
113
    """
114

115
    # precondition
116
    assert isinstance(n, int) and (n > 2), "'N' must been an int and > 2"
117

118
    # beginList: contains all natural numbers from 2 up to N
119
    begin_list = list(range(2, n + 1))
120

121
    ans = []  # this list will be returns.
122

123
    # actual sieve of erathostenes
124
    for i in range(len(begin_list)):
125
        for j in range(i + 1, len(begin_list)):
126
            if (begin_list[i] != 0) and (begin_list[j] % begin_list[i] == 0):
127
                begin_list[j] = 0
128

129
    # filters actual prime numbers.
130
    ans = [x for x in begin_list if x != 0]
131

132
    # precondition
133
    assert isinstance(ans, list), "'ans' must been from type list"
134

135
    return ans
136

137

138
# --------------------------------
139

140

141
def get_prime_numbers(n):
142
    """
143
    input: positive integer 'N' > 2
144
    returns a list of prime numbers from 2 up to N (inclusive)
145
    This function is more efficient as function 'sieveEr(...)'
146

147
    >>> get_prime_numbers(8)
148
    [2, 3, 5, 7]
149
    >>> get_prime_numbers(-1)
150
    Traceback (most recent call last):
151
        ...
152
    AssertionError: 'N' must been an int and > 2
153
    >>> get_prime_numbers("test")
154
    Traceback (most recent call last):
155
        ...
156
    AssertionError: 'N' must been an int and > 2
157
    """
158

159
    # precondition
160
    assert isinstance(n, int) and (n > 2), "'N' must been an int and > 2"
161

162
    ans = []
163

164
    # iterates over all numbers between 2 up to N+1
165
    # if a number is prime then appends to list 'ans'
166
    for number in range(2, n + 1):
167
        if is_prime(number):
168
            ans.append(number)
169

170
    # precondition
171
    assert isinstance(ans, list), "'ans' must been from type list"
172

173
    return ans
174

175

176
# -----------------------------------------
177

178

179
def prime_factorization(number):
180
    """
181
    input: positive integer 'number'
182
    returns a list of the prime number factors of 'number'
183

184
    >>> prime_factorization(0)
185
    [0]
186
    >>> prime_factorization(8)
187
    [2, 2, 2]
188
    >>> prime_factorization(287)
189
    [7, 41]
190
    >>> prime_factorization(-1)
191
    Traceback (most recent call last):
192
        ...
193
    AssertionError: 'number' must been an int and >= 0
194
    >>> prime_factorization("test")
195
    Traceback (most recent call last):
196
        ...
197
    AssertionError: 'number' must been an int and >= 0
198
    """
199

200
    # precondition
201
    assert isinstance(number, int) and number >= 0, "'number' must been an int and >= 0"
202

203
    ans = []  # this list will be returns of the function.
204

205
    # potential prime number factors.
206

207
    factor = 2
208

209
    quotient = number
210

211
    if number in {0, 1}:
212
        ans.append(number)
213

214
    # if 'number' not prime then builds the prime factorization of 'number'
215
    elif not is_prime(number):
216
        while quotient != 1:
217
            if is_prime(factor) and (quotient % factor == 0):
218
                ans.append(factor)
219
                quotient /= factor
220
            else:
221
                factor += 1
222

223
    else:
224
        ans.append(number)
225

226
    # precondition
227
    assert isinstance(ans, list), "'ans' must been from type list"
228

229
    return ans
230

231

232
# -----------------------------------------
233

234

235
def greatest_prime_factor(number):
236
    """
237
    input: positive integer 'number' >= 0
238
    returns the greatest prime number factor of 'number'
239

240
    >>> greatest_prime_factor(0)
241
    0
242
    >>> greatest_prime_factor(8)
243
    2
244
    >>> greatest_prime_factor(287)
245
    41
246
    >>> greatest_prime_factor(-1)
247
    Traceback (most recent call last):
248
        ...
249
    AssertionError: 'number' must been an int and >= 0
250
    >>> greatest_prime_factor("test")
251
    Traceback (most recent call last):
252
        ...
253
    AssertionError: 'number' must been an int and >= 0
254
    """
255

256
    # precondition
257
    assert isinstance(number, int) and (
258
        number >= 0
259
    ), "'number' must been an int and >= 0"
260

261
    ans = 0
262

263
    # prime factorization of 'number'
264
    prime_factors = prime_factorization(number)
265

266
    ans = max(prime_factors)
267

268
    # precondition
269
    assert isinstance(ans, int), "'ans' must been from type int"
270

271
    return ans
272

273

274
# ----------------------------------------------
275

276

277
def smallest_prime_factor(number):
278
    """
279
    input: integer 'number' >= 0
280
    returns the smallest prime number factor of 'number'
281

282
    >>> smallest_prime_factor(0)
283
    0
284
    >>> smallest_prime_factor(8)
285
    2
286
    >>> smallest_prime_factor(287)
287
    7
288
    >>> smallest_prime_factor(-1)
289
    Traceback (most recent call last):
290
        ...
291
    AssertionError: 'number' must been an int and >= 0
292
    >>> smallest_prime_factor("test")
293
    Traceback (most recent call last):
294
        ...
295
    AssertionError: 'number' must been an int and >= 0
296
    """
297

298
    # precondition
299
    assert isinstance(number, int) and (
300
        number >= 0
301
    ), "'number' must been an int and >= 0"
302

303
    ans = 0
304

305
    # prime factorization of 'number'
306
    prime_factors = prime_factorization(number)
307

308
    ans = min(prime_factors)
309

310
    # precondition
311
    assert isinstance(ans, int), "'ans' must been from type int"
312

313
    return ans
314

315

316
# ----------------------
317

318

319
def is_even(number):
320
    """
321
    input: integer 'number'
322
    returns true if 'number' is even, otherwise false.
323

324
    >>> is_even(0)
325
    True
326
    >>> is_even(8)
327
    True
328
    >>> is_even(287)
329
    False
330
    >>> is_even(-1)
331
    False
332
    >>> is_even("test")
333
    Traceback (most recent call last):
334
        ...
335
    AssertionError: 'number' must been an int
336
    """
337

338
    # precondition
339
    assert isinstance(number, int), "'number' must been an int"
340
    assert isinstance(number % 2 == 0, bool), "compare must been from type bool"
341

342
    return number % 2 == 0
343

344

345
# ------------------------
346

347

348
def is_odd(number):
349
    """
350
    input: integer 'number'
351
    returns true if 'number' is odd, otherwise false.
352

353
    >>> is_odd(0)
354
    False
355
    >>> is_odd(8)
356
    False
357
    >>> is_odd(287)
358
    True
359
    >>> is_odd(-1)
360
    True
361
    >>> is_odd("test")
362
    Traceback (most recent call last):
363
        ...
364
    AssertionError: 'number' must been an int
365
    """
366

367
    # precondition
368
    assert isinstance(number, int), "'number' must been an int"
369
    assert isinstance(number % 2 != 0, bool), "compare must been from type bool"
370

371
    return number % 2 != 0
372

373

374
# ------------------------
375

376

377
def goldbach(number):
378
    """
379
    Goldbach's assumption
380
    input: a even positive integer 'number' > 2
381
    returns a list of two prime numbers whose sum is equal to 'number'
382

383
    >>> goldbach(8)
384
    [3, 5]
385
    >>> goldbach(824)
386
    [3, 821]
387
    >>> goldbach(0)
388
    Traceback (most recent call last):
389
        ...
390
    AssertionError: 'number' must been an int, even and > 2
391
    >>> goldbach(-1)
392
    Traceback (most recent call last):
393
        ...
394
    AssertionError: 'number' must been an int, even and > 2
395
    >>> goldbach("test")
396
    Traceback (most recent call last):
397
        ...
398
    AssertionError: 'number' must been an int, even and > 2
399
    """
400

401
    # precondition
402
    assert (
403
        isinstance(number, int) and (number > 2) and is_even(number)
404
    ), "'number' must been an int, even and > 2"
405

406
    ans = []  # this list will returned
407

408
    # creates a list of prime numbers between 2 up to 'number'
409
    prime_numbers = get_prime_numbers(number)
410
    len_pn = len(prime_numbers)
411

412
    # run variable for while-loops.
413
    i = 0
414
    j = None
415

416
    # exit variable. for break up the loops
417
    loop = True
418

419
    while i < len_pn and loop:
420
        j = i + 1
421

422
        while j < len_pn and loop:
423
            if prime_numbers[i] + prime_numbers[j] == number:
424
                loop = False
425
                ans.append(prime_numbers[i])
426
                ans.append(prime_numbers[j])
427

428
            j += 1
429

430
        i += 1
431

432
    # precondition
433
    assert (
434
        isinstance(ans, list)
435
        and (len(ans) == 2)
436
        and (ans[0] + ans[1] == number)
437
        and is_prime(ans[0])
438
        and is_prime(ans[1])
439
    ), "'ans' must contains two primes. And sum of elements must been eq 'number'"
440

441
    return ans
442

443

444
# ----------------------------------------------
445

446

447
def kg_v(number1, number2):
448
    """
449
    Least common multiple
450
    input: two positive integer 'number1' and 'number2'
451
    returns the least common multiple of 'number1' and 'number2'
452

453
    >>> kg_v(8,10)
454
    40
455
    >>> kg_v(824,67)
456
    55208
457
    >>> kg_v(1, 10)
458
    10
459
    >>> kg_v(0)
460
    Traceback (most recent call last):
461
        ...
462
    TypeError: kg_v() missing 1 required positional argument: 'number2'
463
    >>> kg_v(10,-1)
464
    Traceback (most recent call last):
465
        ...
466
    AssertionError: 'number1' and 'number2' must been positive integer.
467
    >>> kg_v("test","test2")
468
    Traceback (most recent call last):
469
        ...
470
    AssertionError: 'number1' and 'number2' must been positive integer.
471
    """
472

473
    # precondition
474
    assert (
475
        isinstance(number1, int)
476
        and isinstance(number2, int)
477
        and (number1 >= 1)
478
        and (number2 >= 1)
479
    ), "'number1' and 'number2' must been positive integer."
480

481
    ans = 1  # actual answer that will be return.
482

483
    # for kgV (x,1)
484
    if number1 > 1 and number2 > 1:
485
        # builds the prime factorization of 'number1' and 'number2'
486
        prime_fac_1 = prime_factorization(number1)
487
        prime_fac_2 = prime_factorization(number2)
488

489
    elif number1 == 1 or number2 == 1:
490
        prime_fac_1 = []
491
        prime_fac_2 = []
492
        ans = max(number1, number2)
493

494
    count1 = 0
495
    count2 = 0
496

497
    done = []  # captured numbers int both 'primeFac1' and 'primeFac2'
498

499
    # iterates through primeFac1
500
    for n in prime_fac_1:
501
        if n not in done:
502
            if n in prime_fac_2:
503
                count1 = prime_fac_1.count(n)
504
                count2 = prime_fac_2.count(n)
505

506
                for _ in range(max(count1, count2)):
507
                    ans *= n
508

509
            else:
510
                count1 = prime_fac_1.count(n)
511

512
                for _ in range(count1):
513
                    ans *= n
514

515
            done.append(n)
516

517
    # iterates through primeFac2
518
    for n in prime_fac_2:
519
        if n not in done:
520
            count2 = prime_fac_2.count(n)
521

522
            for _ in range(count2):
523
                ans *= n
524

525
            done.append(n)
526

527
    # precondition
528
    assert isinstance(ans, int) and (
529
        ans >= 0
530
    ), "'ans' must been from type int and positive"
531

532
    return ans
533

534

535
# ----------------------------------
536

537

538
def get_prime(n):
539
    """
540
    Gets the n-th prime number.
541
    input: positive integer 'n' >= 0
542
    returns the n-th prime number, beginning at index 0
543

544
    >>> get_prime(0)
545
    2
546
    >>> get_prime(8)
547
    23
548
    >>> get_prime(824)
549
    6337
550
    >>> get_prime(-1)
551
    Traceback (most recent call last):
552
        ...
553
    AssertionError: 'number' must been a positive int
554
    >>> get_prime("test")
555
    Traceback (most recent call last):
556
        ...
557
    AssertionError: 'number' must been a positive int
558
    """
559

560
    # precondition
561
    assert isinstance(n, int) and (n >= 0), "'number' must been a positive int"
562

563
    index = 0
564
    ans = 2  # this variable holds the answer
565

566
    while index < n:
567
        index += 1
568

569
        ans += 1  # counts to the next number
570

571
        # if ans not prime then
572
        # runs to the next prime number.
573
        while not is_prime(ans):
574
            ans += 1
575

576
    # precondition
577
    assert isinstance(ans, int) and is_prime(
578
        ans
579
    ), "'ans' must been a prime number and from type int"
580

581
    return ans
582

583

584
# ---------------------------------------------------
585

586

587
def get_primes_between(p_number_1, p_number_2):
588
    """
589
    input: prime numbers 'pNumber1' and 'pNumber2'
590
            pNumber1 < pNumber2
591
    returns a list of all prime numbers between 'pNumber1' (exclusive)
592
            and 'pNumber2' (exclusive)
593

594
    >>> get_primes_between(3, 67)
595
    [5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61]
596
    >>> get_primes_between(0)
597
    Traceback (most recent call last):
598
        ...
599
    TypeError: get_primes_between() missing 1 required positional argument: 'p_number_2'
600
    >>> get_primes_between(0, 1)
601
    Traceback (most recent call last):
602
        ...
603
    AssertionError: The arguments must been prime numbers and 'pNumber1' < 'pNumber2'
604
    >>> get_primes_between(-1, 3)
605
    Traceback (most recent call last):
606
        ...
607
    AssertionError: 'number' must been an int and positive
608
    >>> get_primes_between("test","test")
609
    Traceback (most recent call last):
610
        ...
611
    AssertionError: 'number' must been an int and positive
612
    """
613

614
    # precondition
615
    assert (
616
        is_prime(p_number_1) and is_prime(p_number_2) and (p_number_1 < p_number_2)
617
    ), "The arguments must been prime numbers and 'pNumber1' < 'pNumber2'"
618

619
    number = p_number_1 + 1  # jump to the next number
620

621
    ans = []  # this list will be returns.
622

623
    # if number is not prime then
624
    # fetch the next prime number.
625
    while not is_prime(number):
626
        number += 1
627

628
    while number < p_number_2:
629
        ans.append(number)
630

631
        number += 1
632

633
        # fetch the next prime number.
634
        while not is_prime(number):
635
            number += 1
636

637
    # precondition
638
    assert (
639
        isinstance(ans, list)
640
        and ans[0] != p_number_1
641
        and ans[len(ans) - 1] != p_number_2
642
    ), "'ans' must been a list without the arguments"
643

644
    # 'ans' contains not 'pNumber1' and 'pNumber2' !
645
    return ans
646

647

648
# ----------------------------------------------------
649

650

651
def get_divisors(n):
652
    """
653
    input: positive integer 'n' >= 1
654
    returns all divisors of n (inclusive 1 and 'n')
655

656
    >>> get_divisors(8)
657
    [1, 2, 4, 8]
658
    >>> get_divisors(824)
659
    [1, 2, 4, 8, 103, 206, 412, 824]
660
    >>> get_divisors(-1)
661
    Traceback (most recent call last):
662
        ...
663
    AssertionError: 'n' must been int and >= 1
664
    >>> get_divisors("test")
665
    Traceback (most recent call last):
666
        ...
667
    AssertionError: 'n' must been int and >= 1
668
    """
669

670
    # precondition
671
    assert isinstance(n, int) and (n >= 1), "'n' must been int and >= 1"
672

673
    ans = []  # will be returned.
674

675
    for divisor in range(1, n + 1):
676
        if n % divisor == 0:
677
            ans.append(divisor)
678

679
    # precondition
680
    assert ans[0] == 1 and ans[len(ans) - 1] == n, "Error in function getDivisiors(...)"
681

682
    return ans
683

684

685
# ----------------------------------------------------
686

687

688
def is_perfect_number(number):
689
    """
690
    input: positive integer 'number' > 1
691
    returns true if 'number' is a perfect number otherwise false.
692

693
    >>> is_perfect_number(28)
694
    True
695
    >>> is_perfect_number(824)
696
    False
697
    >>> is_perfect_number(-1)
698
    Traceback (most recent call last):
699
        ...
700
    AssertionError: 'number' must been an int and >= 1
701
    >>> is_perfect_number("test")
702
    Traceback (most recent call last):
703
        ...
704
    AssertionError: 'number' must been an int and >= 1
705
    """
706

707
    # precondition
708
    assert isinstance(number, int) and (
709
        number > 1
710
    ), "'number' must been an int and >= 1"
711

712
    divisors = get_divisors(number)
713

714
    # precondition
715
    assert (
716
        isinstance(divisors, list)
717
        and (divisors[0] == 1)
718
        and (divisors[len(divisors) - 1] == number)
719
    ), "Error in help-function getDivisiors(...)"
720

721
    # summed all divisors up to 'number' (exclusive), hence [:-1]
722
    return sum(divisors[:-1]) == number
723

724

725
# ------------------------------------------------------------
726

727

728
def simplify_fraction(numerator, denominator):
729
    """
730
    input: two integer 'numerator' and 'denominator'
731
    assumes: 'denominator' != 0
732
    returns: a tuple with simplify numerator and denominator.
733

734
    >>> simplify_fraction(10, 20)
735
    (1, 2)
736
    >>> simplify_fraction(10, -1)
737
    (10, -1)
738
    >>> simplify_fraction("test","test")
739
    Traceback (most recent call last):
740
        ...
741
    AssertionError: The arguments must been from type int and 'denominator' != 0
742
    """
743

744
    # precondition
745
    assert (
746
        isinstance(numerator, int)
747
        and isinstance(denominator, int)
748
        and (denominator != 0)
749
    ), "The arguments must been from type int and 'denominator' != 0"
750

751
    # build the greatest common divisor of numerator and denominator.
752
    gcd_of_fraction = gcd_by_iterative(abs(numerator), abs(denominator))
753

754
    # precondition
755
    assert (
756
        isinstance(gcd_of_fraction, int)
757
        and (numerator % gcd_of_fraction == 0)
758
        and (denominator % gcd_of_fraction == 0)
759
    ), "Error in function gcd_by_iterative(...,...)"
760

761
    return (numerator // gcd_of_fraction, denominator // gcd_of_fraction)
762

763

764
# -----------------------------------------------------------------
765

766

767
def factorial(n):
768
    """
769
    input: positive integer 'n'
770
    returns the factorial of 'n' (n!)
771

772
    >>> factorial(0)
773
    1
774
    >>> factorial(20)
775
    2432902008176640000
776
    >>> factorial(-1)
777
    Traceback (most recent call last):
778
        ...
779
    AssertionError: 'n' must been a int and >= 0
780
    >>> factorial("test")
781
    Traceback (most recent call last):
782
        ...
783
    AssertionError: 'n' must been a int and >= 0
784
    """
785

786
    # precondition
787
    assert isinstance(n, int) and (n >= 0), "'n' must been a int and >= 0"
788

789
    ans = 1  # this will be return.
790

791
    for factor in range(1, n + 1):
792
        ans *= factor
793

794
    return ans
795

796

797
# -------------------------------------------------------------------
798

799

800
def fib(n: int) -> int:
801
    """
802
    input: positive integer 'n'
803
    returns the n-th fibonacci term , indexing by 0
804

805
    >>> fib(0)
806
    1
807
    >>> fib(5)
808
    8
809
    >>> fib(20)
810
    10946
811
    >>> fib(99)
812
    354224848179261915075
813
    >>> fib(-1)
814
    Traceback (most recent call last):
815
    ...
816
    AssertionError: 'n' must been an int and >= 0
817
    >>> fib("test")
818
    Traceback (most recent call last):
819
    ...
820
    AssertionError: 'n' must been an int and >= 0
821
    """
822

823
    # precondition
824
    assert isinstance(n, int) and (n >= 0), "'n' must been an int and >= 0"
825

826
    tmp = 0
827
    fib1 = 1
828
    ans = 1  # this will be return
829

830
    for _ in range(n - 1):
831
        tmp = ans
832
        ans += fib1
833
        fib1 = tmp
834

835
    return ans
836

837

838
if __name__ == "__main__":
839
    import doctest
840

841
    doctest.testmod()
842