Arrays and Matrices

Arrays and Matrices

1

Sieve of Eratosthenes

counting primes

arrays in Python

2

Matrices

matrices as lists of arrays

finding the minimum

finding saddle points

MCS 275 Lecture 3

Programming Tools and File Management

Jan Verschelde, 13 January 2017

Programming Tools (MCS 275)

Arrays and Matrices

L-3

15 January 2016

1 / 38

Arrays and Matrices

1

Sieve of Eratosthenes

counting primes

arrays in Python

2

Matrices

matrices as lists of arrays

finding the minimum

finding saddle points

Programming Tools (MCS 275)

Arrays and Matrices

L-3

15 January 2016

2 / 38

the Sieve of Eratosthenes

Input/Output specification:

input : a natural number n

output : all prime numbers �� n

Running factorization in primes for all numbers �� n

is too expensive.

Sieve of Eratosthenes:

1

Boolean table isprime[i] records prime numbers:

if i is prime, then isprime[i] == True,

otherwise isprime[i] == False.

2

All multiples of prime numbers are not prime:

for all isprime[i]: isprime[i*k] = False.

Programming Tools (MCS 275)

Arrays and Matrices

L-3

15 January 2016

3 / 38

all primes less than 10

T = True, F = False

i

0

2

3

2

T

T

T

3

T

T

T

4

T

F

F

5

T

T

T

6

T

F

F

7

T

T

T

8

T

F

F

9

T

T

F

10

T

F

F

Initially, all entries in the table are True.

The algorithm uses a double loop:

1

2

the first loop runs for i from 2 to n;

the second loop runs only if i is prime,

setting to False all multiples of i.

Be more efficient, first loop: while (i < n//i).

Programming Tools (MCS 275)

Arrays and Matrices

L-3

15 January 2016

4 / 38

Arrays and Matrices

1

Sieve of Eratosthenes

counting primes

arrays in Python

2

Matrices

matrices as lists of arrays

finding the minimum

finding saddle points

Programming Tools (MCS 275)

Arrays and Matrices

L-3

15 January 2016

5 / 38

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download