After struggling with this for a little bit, and not finding any satisfactory solutions online, I was able to come up with this. Save the following script and add it to your startup applications:
#!/bin/bash gconftool-2 --type List --list-type String \ --set /apps/panel/general/toplevel_id_list "[]"
Note: This will hide all your panels. I’ve only tried this in Ubuntu 10.04 (Lucid).
0 Comments »Here’s a brief summary of PRIME1 on SPOJ.
Input on STDIN:
Output on STDOUT: For each test, output every prime p such that m <= p <= n, one number per line, with test cases separated by an empty line.
The source file has a limit of 50KB and a time limit of 6 seconds. Here’s what I ended up doing in Perl:
1 @primes = (2,3,5,7,11,13,17,19,...,31607);
2
3 <>;
4 undef $/;
5 for (split "\n", <>) {
6 ($min, $max) = split;
7 $min = 2 if $min == 1;
8
9 @num_list = undef;
10 for $prime (@primes) {
11 if ($prime*int($min/$prime) < $min) {
12 $mult = int($min/$prime)+1;
13 } else {
14 $mult = int($min/$prime);
15 }
16
17 $mult = 2 if $mult == 1;
18
19 for (; $prime*$mult <= $max; $mult++) {
20 $num_list[$prime*$mult-$min] = 1;
21 }
22 last if $prime*$prime > $max;
23 }
24 for $index (0..$max-$min) {
25 print $index+$min, "\n" if $num_list[$index] != 1;
26 }
27 print "\n";
28 }
The first line is truncated, which I explain below. If you want to follow along, here’s the full source.
My best time with this program was 4.20s, placing me 7th place among Perl submissions (although only 15 people total have written Perl programs that pass PRIME1). For what it’s worth, SPOJ runs Perl programs under Perl 5.10.0.
Note that when trying to write for speed, the program is much faster without strict mode or warnings on, hence the slight sloppiness.
Line 1 is truncated and contains all the prime numbers from 2 to 31607. When looking at the divisors of a number, we only need to examine those possible divisors that are less than or equal to the square root of the number. The Primality test article on Wikipedia explains why (along with other techniques) in detail, but basically, if a divides c, then there’s some b such that ab = c, and one of those is going to be above sqrt(c).
Since sqrt(1,000,000,000) is roughly 31622, we only need to check the primes up to 31622. The largest prime less than 31622 is 31607, hence the upper limit of the array @primes.
Line 3 discards the first line of input, the number of test cases. Line 4 turns off “\n” as the line delimiter, so that <> returns all the input at once, and line 5 loops over the input, splitting it up by newlines. Doing it this way was a few hundredths of a second shorter than just the straightforward while (<>).
At line 7, the algorithm outputs 1 as a prime number if 1 happens to be given as the lower limit, so we raise the limit if this is the case.
Line 9 is an anomaly, since the proper way to initialize an empty list is @num_list = (). However, doing it this improper way (which just sets $num_list[0] to undef) shaved a few hundredths of a second off. Omitting the declaration altogether caused incorrect output according to SPOJ, but I wasn’t able to find a test case that demonstrated this, nor could I figure out a reason for it, since in Perl, omitting the statement should result in the same array as initializing its first member to undef (I suspect the whole problem may be due to old values of @num_list being used for the test after, but I haven’t dug too deep into how the array ends up being scoped).
The rest of the program implements the Sieve of Eratosthenes for the given range [$min, $max]. First, for each prime in the list, it initializes $mult to the smallest value such that $prime*$mult falls within the range, and then removes each multiple of that prime (and thus a composite number) from the list by marking its position in @num_list with a 1.
Note that the range is shifted so that $min maps to $num_list[0], etc.
The for loop on line 19 has no initialization since we already initialized $mult above.
We don’t need to check any primes greater than the square root of the max of the range, as I explained earlier. Since sqrt is a relatively expensive operation, instead of checking for $prime > sqrt($max), we square both sides and check for the equivalent $prime*$prime > $max.
Finally, we go through and print all the array entries that weren’t marked as 1, adding $min to the array indices we’re looping through to put them back into the proper range.