CCC '05 J2 - RSA Numbers

View as PDF

Submit solution

Points: 3
Time limit: 2.0s
Memory limit: 64M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
Canadian Computing Competition: 2005 Stage 1, Junior #2

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 \dots 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

CCC problem statements in large part from the PEG OJ


Comments


  • 2
    jaihysc  commented on Dec. 9, 2019, 6:38 p.m.

    It should be noted that the range inputted is inclusive.


    • 3
      Super_User  commented on Dec. 28, 2019, 10:37 p.m.

      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.

      It explains in the description. The range is 10-12 and the numbers tested were 10, 11 & 12.