Algorithms -- 2009-2010 -- info.uvt.ro/Laboratory 1

Quick links: front; laboratories agenda, 1, 2, 3, 4, 5, 6, 7, evaluation, tools, references.

Notes

Python notes (everything, except functions):
- Python -- First Steps (in English);
- Python -- Primii Paşi (in Romanian);

Laboratory / seminar problem set 1:
- in English (from profesor Daniela Zaharie);
- in Romanian (from profesor Daniela Zaharie);

Exercises

From the problem set above, exercises:

problem 7 (for en), or problem 8 (for ro), points:
- a: Computing the sum of all digits of number n. For instance for n = 26326 one obtains the value 19.
- f: Deciding if n is prime or not (the algorithm should return true if the number is prime and false otherwise.
- g: Decomposing n in prime factors. For instance for 490 = 2^1 * 5^1 * 7^2 one obtains the following set of prime factors: {2, 5, 7} and their corresponding exponents: {1, 1, 2}.

Assignment

For submission please follow: assignment 1.

From the problem set above, exercises:

problem 7 (for en), or problem 8 (for ro), points:
- c: Constructing the set of all digits of n. For instance, for the value 26326 one obtain the set {2, 3, 6}. Hints:
  - use a list with 10 elements (from 0 to 9) with boolean values (True or False);
- d: Finding all binary digits of n.
  - use a list to hold the digits (to print them in the correct order);
- e: Finding all proper divisors of n (divisors which are not 1 or n).

Solutions to exercises

the sum of the digits of a number:

n = input ("n = ")
s = 0
while n > 0 :
    d = n % 10
    n = n / 10
    s += d
print s

deciding if a number is prime or not:

from math import sqrt

n = input ("n = ")

# p -> if n is prime or not
if n <= 1 :
    p = False
elif n <= 3 :
    p = True
elif n % 2 == 0 :
    p = False
else :
    l = int (sqrt (n))
    p = True
    for d in range (3, l + 1, 2) :
        if n % d == 0 :
            p = False
            break

if p :
    print "prime"
else :
    print "not prime"

determining the prime factors of a number:
- variant a:

from math import sqrt

n = input ("n = ")

for d in range (2, int (sqrt (n)) + 1) :
    c = 0
    while n % d == 0 :
        c += 1
        n /= d
    if c > 0 :
        print d, "^", c

- variant b:

n = input ("n = ")
d = 2
c = 0
while n > 1 :
    if n % d == 0 :
        c += 1
        n /= d
    else :
        if c > 0 :
            print d, "^", c
        d += 1
        c = 0
if c > 0 :
    print d, "^", c

Ciprian Dorin Crăciun, ccraciun@info.uvt.ro