main thread

בשאלה 3ב, אני מניח שאפשר לקרוא לפונקציה שבנינו ב-3א ואין צורך לכתוב מחדש, נכון?

Should I consider 0 to be a prefect number when counting the amount of perfect numbers up to limit?

for example:

should count_perfect_numbers(6) return 2 (for 0 and 6) or just 1 (for 6)?

According to the definition of perfect numbers 0 is not a perfect number.

Try to think which numbers (that are not 0 itself) are it's divisors and whether their sum is 0.

בשאלה 3 א

האם עבור הקלט 1 הפונקציה אמורה להחזיר 0?

כי 1 הוא המחלק היחיד של עצמו אז אני לא בטוחה מה אמורים לעשות במקרה קצה זה

Yes.

We are only interested in divisors of n that are not equal to n.

For n=1 there are no such divisors, therefore the sum is 0.

in question are we only interested in prime divisors?

No, a divisor of *n* is any integer that divides *n* with no remainder.

Hello,

I have a general question: If I created an algorithm that runs n**0.5 iterations, but each iteration has two conditions: would it be considered as 0(n**0.5) or does the "time of verification on the first condition at worst case" also considered as a step?

Thank you in advance.

If at every iteration of the loop you test c=2 (or eight, or twenty) conditions, the complexity of your algorithm increases by a factor of c compared with an algorithm which tests only a single condition.

The asymptotic running time analysis (which is expressed in the big O notation) does not care about multiplicative (or additive) factors, only about the type of response of the running time (e.g. linear, quadratic) to changes in the problem size.

Therefore as long as the complexity of every iteration of the loop is constant (i.e., independent of n) you're on the safe side.

באופן כללי וגם להמשך הקורס, כשאומרים מס' שלם וחיובי, מתכוונים גם ל-0?

כלומר בהקשר של השאלה: 0 הוא קלט אפשרי?

The definition of a positive number (out there in the big world, not just in this course) is a number greater than 0.

If we wanted to include zero we'd say "nonnegative number".

about running-time in 3c. (count perfect numbers) what is the estimited running time youre expecting?

if my function runs to 100000 in about 25 secs is that too slow??

The exact running time depends on the computer you're running on.

However, if you implemented an O(sqrt(n)) algorithm in part (a) you should be all good (unless you did something exquisitely bizarre).

Hi,

You first wrote 'we want to know how many perfect numbers under 100000 there are', but then you also wrote 'the function receives a limit and returns how many perfect numbers smaller or equal to the limit there are'.

An implementation for the first case will return

count_perfect_numbers(28)

1

While the second one:

count_perfect_numbers(28)

2

Which one is it?

Hope you will give both cases full credit since probably most students already submitted their HW and didn't consider both cases.

Thanks