TopCoder Statistics - Problem Statement

Problem Statement

The Sieve of Erathosthenes is an ancient method used to find all prime numbers between 2 and a given upper bound maxNum, inclusive. It works like this:

make a list of all numbers between 2 and maxNum, inclusive
for x = 2 to maxNum
   if x is not scratched
      for y = 2 to maxNum/x
         if x*y is not scratched, scratch x*y
      end for
   end if
end for

In this fashion, every composite number in the range will get scratched while every prime number will remain unscratched. Return the last number which gets scratched when the Sieve of Eratosthenes is run with the given maxNum.

Definition

Class:: SieveOfEratosthenes
Method:: lastScratch
Parameters:: int
Returns:: int
Method signature:: int lastScratch(int maxNum)
(be sure your method is public)

Constraints

maxNum will be between 4 and 2000000000 (2*109), inclusive.

Examples

18

Returns: 15

When x=2, the numbers 4, 6, 8, 10, 12, 14, 16, and 18 are scratched. When x=3, only 9 and 15 are scratched (other multiples like 6 and 12 were already scratched in a previous step). For x=5,7,11,13 and 17, there are no new scratches. Therefore, the answer is 15.
5

Returns: 4

2, 3 and 5 are all primes, so the only scratched number is 4.
100

Returns: 91
400

Returns: 361
2000000000

Returns: 1999878319
8

Returns: 8
1999999998

Returns: 1999878319
1999999254

Returns: 1999878319
1999999112

Returns: 1999878319
1999999066

Returns: 1999878319
1999999008

Returns: 1999878319
1999878319

Returns: 1999878319
1999878168

Returns: 1999073521
1999827445

Returns: 1999073521
1999599033

Returns: 1999073521
1999169514

Returns: 1999073521
1999159633

Returns: 1999073521
1999073520

Returns: 1998626411
1999072210

Returns: 1998626411
1998351843

Returns: 1998179401
1998131217

Returns: 1998089999
1997833237

Returns: 1997553587
1997665189

Returns: 1997553587
1997150393

Returns: 1996927969
1996816063

Returns: 1996749221
1996611676

Returns: 1996570489
1996416006

Returns: 1996212557
1995872735

Returns: 1995587359
1995314573

Returns: 1994247649
1111111111

Returns: 1110955561
1073741824

Returns: 1073610467
1000000000

Returns: 999634589
999999999

Returns: 999634589
594823321

Returns: 594628189
134217728

Returns: 134165873
43046721

Returns: 43046657
20511149

Returns: 20457529
16777216

Returns: 16777207
2097152

Returns: 2093809
707281

Returns: 703921
262144

Returns: 259081
32768

Returns: 32761
24389

Returns: 23707
6561

Returns: 6557
4096

Returns: 4087
1024

Returns: 961
841

Returns: 841
512

Returns: 437
256

Returns: 247
128

Returns: 121
81

Returns: 77
64

Returns: 49
32

Returns: 25
29

Returns: 25
16

Returns: 15
9

Returns: 9
1999878318

Returns: 1999073521
7

Returns: 6
6

Returns: 6
4

Returns: 4
10

Returns: 9
25

Returns: 25
48

Returns: 35
1987654321

Returns: 1987643873
1897231767

Returns: 1895992849
1916425729

Returns: 1916425729
1999878317

Returns: 1999073521

Statistics

Problem Statement for "SieveOfEratosthenes"

Problem Statement

Definition

Constraints

Examples