2005 Canadian Computing Competition, Stage 1

Problem J2: RSA Numbers

When a credit card number is sent through the Internet it must be protected so that other people cannot see it. Many web browsers use a protection based on "RSA Numbers."

A number is an RSA number if it has exactly four divisors. In other words, there are exactly four numbers that divide into it evenly. For example, 10 is an RSA number because it has exactly four divisors (1, 2, 5, 10). 12 is not an RSA number because it has too many divisors (1, 2, 3, 4, 6, 12). 11 is not an RSA number either. There is only one RSA number in the range 10...12.

Write a program that inputs a range of numbers and then counts how many numbers from that range are RSA numbers. You may assume that the numbers in the range are less than 1000.

Sample Input 1

10
12

Sample Output 1

The number of RSA numbers between 10 and 12 is 1

Sample Input 2

11
15

Sample Output 2

The number of RSA numbers between 11 and 15 is 2

All Submissions
Best Solutions

Point Value: 3
Time Limit: 2.00s
Memory Limit: 16M
Added: Sep 29, 2008

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

I observed that RSA numbers will only be in the form of p^3 or p1 * p2, where p,p1,p2 are prime numbers. But how do I test it?

I would first ask that for 'observations' like this, keep it to yourself, in fact, this comment has no meaning. Now, to answer your question, you have made an interesting observation, but isn't it easier to just use brute force to solve this?, in a contest, if you do it this way, it would be harder right? Now, since you made this'observation', please don't ask on how do you test it, this defeats the purpose of a question

Sorry for that. I thought the comment section was for this kind of stuff. I will not ask something like that again. Also thanks for answering my question.

no problem, and by brute force, i meant the algorithm, you should have used for loops and if statements to solve this, instead of just hard-coding by putting already calculated by hand numbers into an array, look at my submission for implementation details

Thank you for your help.