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

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

## Notes

• Laboratory / seminar problem set 1:

## 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
```