CSE 232

Fall

2017

Programming Project 03

This assignment is worth

2

0

points (

2

% of the course grade) and must be

completed and tu

rned in

before 11:59 on Monday,

September

25

th

.

Assignment Overview

This assignment will give y

o

u more experience on the use of loops and conditionals, and introduce the

use of functions.

Background

There a

re all sorts of special numbers

.

Take a look sometime at

http://mathworl

d.wolfram.com/topics/SpecialNumbers.html

for a big list.

We are going to look at two

classes of special numbers:

k

-

hyperperfect

numbers and

smooth

numbers

Prime Factors

The prime factors of any integer

should be familiar.

You find all the prime integers

that divide exactly

(without remainder) into an integer. We exclude 1 (which is a factor of every integer) and the number

itself (which, again, is a prime factor of every particular number).

for example, the prime factors of 30 are 2,3,5 since 2*3*5=30. N

ote that 6, 15 and 10 are also

factors but they are

not

prime

factors.

take a look at

https://en.wikipedia.org/wiki/Table_of_prime_factors

for a table of the prime

factors of many number

s.

B

-

smooth Numbers

A number is B

-

smooth

https://en.wikipedia.org/wiki/Smooth_number

if none of its prime factors are

greater than the value B.

For example, the list of 5

-

smooth numbers (numbers

whose prime factors are

5 or less) are listed in

https://oeis.org/A051037

. 30, as seen above, is a 5

-

s

mooth number. It would

also be 6

-

smooth, 7

-

smooth, etc.

k

-

hyperperfect numbers

We saw counting the divisors of

a number in project 2. Here we are going to sum all the divisors of a

number. A number

n

is k hyperperfect for some

k

if the following equality holds:

n = 1 + k*(sum_of_divisors(n)

-

n

1)

For example, 28 is 1

-

hyperperfect, meaning that the sum of its d

ivisors (1+2+4+7+14+28)

minus the 28 itself

equals 28. These were traditionally called

perfect

numbers.

21 is 2

-

hyperperfect. Applying the formula:

o

sum_of_divisors(21) = (1+3+7+21) = 32

o

The value in parentheses is then (32

21

1) = 10

o

k =2, so 2

* 10 = 20

o

20 + 1 = 21.

https://en.wikipedia.org/wiki/Hyperperfect_number

gives a list of

k

-

hyperperfect

numbers.

Project Description / Specification

Warning

First, a warning. In this and

in all future projects we will

provide

exactly

our function specifications:

the function name, its return type, its arguments and each argument's type.

The functions will be tested

individually in Mimir using these exact

function specification

s

. If you do

not follow the function

specifications, these independent tests of your functions will fail. Do not change the function

declarations!

Functions

function

:

biggest_prime

: return is

long

. Argument

is a single

long

n

.

Returns the largest prime

factor of

n

.

function

:

sum_of_divisors

: return is

long

.

Argument is a single

long

n

.

Sums up all the

divisors of the argument

n

and returns that sum.

function

:

k_hyperperfect

: return is

long

. Arguments are:

long

n

.

The number we are checking

long k_max

. The maximum

k

value

considered

.

The algorithm searches for a

k

from

1

up to and including

k_max

to test if the input

number

n

is k

-

hyperperfect for

that

k

. The first

k

in the range

1

to

k_max

is returned where

the input

n

proves to

be

k

-

hyperperfect. If

n

is not k

-

hyp

erperfect for any

k

from

1

to

k_max

, the

function returns 0.

k_hyperperfect

should utilize

sum_of_divisors

in its calculations.

function

:

b_smooth

: return is

bool

. Argument

are:

long

n

.

The number being checked

long b

. The prime factor being checked.

Ret

urns

true

if the input

n

is

b

smooth,

false

otherwise.

b_smooth

should utilize

biggest_prime

in its calculations.

Input and Output

and

main

We have the ability in Mimir to test your functions individually, but for this project let's

also

do the

followi

ng for the main program (which you will also write)

which you can see tests for when you turn

in the program. We will

eventually

the functions as specified

independent

of your main, but

for this

project we will test the output of main as follows:

takes in

3 numbers from input:

n, k_max, b

prints out the foll

owing 4 numbers, all space separated, on a single line

o

the

biggest_

prime

of

n

o

the

sum_of_divisors

of

n

o

the

k_hyperperfect

of

n

using

k_max

o

the

b_smooth

of

n

using

b

as we are working only with

longs, we

do not need

either

setprecision

or

fixed

as there is a Boolean result for

b_smooth

, we will use

cout << boolalpha;

for Boolean

output.

we guarantee that no number will exceed the size of a

long

Deliverables

proj03

.cpp

--

your source code solution

includin

g the provided main

(

remember to include your

section, the date, project number

and comments in this file

).

1)

In mimir this is Project 03

-

smooth and k

-

hyperperfect

2)

You are provided with a proj03/proj03.cpp file in

the directory above

. The

.cpp file will sta

rt

blank.

General

Hints:

1.

You

can write as many functions are you like over and above the ones I

have specified.

a.

M

ake sure you write the requested functions exactly as specified. They will be tested

individually according to that specification.

2.

The functi

ons

returns

alone

may not be very informative

.

Don't feel restricted to meeting the test

criteria right away.

Feel free to place lots of output statements in your functions s

o you can see

what is going on and then modify the main later to meet the specifi

c test requirements.

3.

Develop

the functions one at a time and run the appropriate test case to see that the function works!

a.

Don't write everything all at once, write one function at a time, test it and make sure it

works.

Specific Hints

If we were more kno

wledgeable about algorithms we could discuss how to be efficient about these

checks, but for now we would just like them to work. Here are some pretty specific suggestions, but

feel free to work it out for yourself

biggest_prime

:

The simplest, but not ve

ry efficient, algorithm

for listing all the prime factors of a number

is called

"prime factorization by division" method. You do something like the following (let

's use 300 as an

example):

The start. prime_list:

empty

number:

300

start with a divisor of 2

(a prime). If the number divides evenly by 2, do so, making 2 a prime

factor: prime_list:

2

number:

150

can you divide by 2 again? If so keep doing so until you no longer can. We can one more time:

prime_list:

2,

2

number

:

75

OK, now try 3 (a prime number).

Does it divide evenly into 75? It does, so do the work again

prime_list:

2,2,3

number:

25

Any more 3's? Go fish (wait, wrong game). OK, no more 3's

On to 4. 4 you say? Yes, for simplicity's sake

(that is, how you write your loop)

you could now

check 4. Ho

wever

,

two things:

o

4 isn't prime but

o

the number we have remaining cannot possible be evenly divisible by 4, since it is no

longer evenly divisible by 2 (we checked, remember).

o

So we check 4, doesn't work, on to 5

Can we divide evenly by 5? We can

prime_li

st:

2,2,3,5

number:

5

Can we do 5 again? Yes.

prime_list:

2,2,3,5,5

number:

1

We hit 1, we are done and we have our list of prime factors.

You need to pull out

the largest prime factor along the way and return it.

sum_of_divisors

:

You are going to chec

k for each number from 1 to n

to see

if it divides evenly into n

(obviously 1

and n will)

. If it

does then you add it to the sum of divisors

You can be more efficient than that, but it takes a little thought. That would matter for a big

number.