Velocity Reviews > Re: PRIME1 (SPOJ)

# Re: PRIME1 (SPOJ)

Ben Bacarisse
Guest
Posts: n/a

 10-19-2010
superpollo <(E-Mail Removed)> writes:

> superpollo ha scritto:
>> ok, the problem is:
>>
>> https://www.spoj.pl/problems/PRIME1/

> ...
>
> i think i made kind of an improvment, thanks to suggestion in an
> italian math newsgroup:

Because on-line judges don't comment on program style, I'll offer some
C-related comments. If this were comp.programming, I have things to say

> #include <stdio.h>
> #include <stdlib.h>
> #include <stdbool.h>
> #define HOWMANYPRIMES 3401
>
> unsigned primes[HOWMANYPRIMES] = {
> 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59,

<snip lots of primes>
> 31567, 31573, 31583, 31601, 31607
> };

Humans are bad at counting but computers do it well. Rather than tie
the correctness of the program to all sorts of things being just right
you can let the compiler help out:

unsigned primes[] = {
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59,
...
31567, 31573, 31583, 31601, 31607
};

If you need to know how many primes you've now got you can define this
afterwards rather than before:

#define HOWMANYPRIMES (sizeof primes / sizeof primes[0])

> bool is_prime(unsigned long x)
> {
> bool prime;
> unsigned i;
> if (x <= 31607) {

Again, rather than link lots of parts of the program to the maximum
expected input (31607 is the largest prime less than the sqrt of the
largest input the program should be able to deal with) you could write

if (x <= primes[HOWMANYPRIMES - 1]) {

> prime = false;
> for (i = 0; i < HOWMANYPRIMES; i++) {
> if (x == primes[i]) {
> prime = true;
> break;
> }
> }

You don't need to test over 3400 primes to know that 6 is not prime.
Once you see 7 you know that 6 is not there. I know I was not going to
make algorithmic comments but there is a C issue here: know the standard
library! There is a function bsearch, that can search a sorted array
for an item. Whether it pays to use it will depend on the pattern of
inputs the program gets but it's worth a try.

> } else {
> prime = true;
> for (i = 0; i < HOWMANYPRIMES && primes[i] * primes[i] <= x; i++) {
> if (!(x % primes[i])) {
> prime = false;
> break;
> }
> }
> }
> return prime;
> }

Rather than use break so much, many C programmers would use an early
return. The auxiliary bool variable then becomes obsolete:

bool is_prime(unsigned long x)
{
unsigned i;
if (x <= 31607) {
for (i = 0; i < HOWMANYPRIMES; i++)
if (x == primes[i])
return true;
return false;
}
else {
for (i = 0; i < HOWMANYPRIMES && primes[i] * primes[i] <= x; i++)
if (!(x % primes[i]))
return false;
return true;
}
}

Not everyone agrees on this. Look up "single entry single exit" and you
will probably be able to find some good counter arguments.

<snip>
--
Ben.

Ben Bacarisse
Guest
Posts: n/a

 10-19-2010
superpollo <(E-Mail Removed)> writes:

> Ben Bacarisse ha scritto:

<snip>
>> Not everyone agrees on this. Look up "single entry single exit" and you
>> will probably be able to find some good counter arguments.
>>
>> <snip>

>
> yeah, this sound like some interesting stylistic issue ... if i
> understand it correctly, it seems like there is a tradeoff between
> "single exit" and "natural loop termination": cannot have both, yes?

Well, you can have both -- sometimes but not always. There are examples
where there is no conflict between them.

> granted having one auxvar less is an even better deal...

For me, yes, but I did want you to know that there is some controversy
here.

--
Ben.

Ben Bacarisse
Guest
Posts: n/a

 10-19-2010
superpollo <(E-Mail Removed)> writes:

> Ben Bacarisse ha scritto:
>> superpollo <(E-Mail Removed)> writes:
>>
>>> Ben Bacarisse ha scritto:

>> <snip>
>>>> Not everyone agrees on this. Look up "single entry single exit" and you
>>>> will probably be able to find some good counter arguments.
>>>>
>>>> <snip>
>>> yeah, this sound like some interesting stylistic issue ... if i
>>> understand it correctly, it seems like there is a tradeoff between
>>> "single exit" and "natural loop termination": cannot have both, yes?

>>
>> Well, you can have both -- sometimes but not always. There are examples
>> where there is no conflict between them.

>
> can you show me how, in the code:
>
> bool is_prime(unsigned long x)
> {
> unsigned i;
> if (x == 1) {
> return false;
> } else {
> for (i = 0; i < HOWMANYPRIMES && primes[i] * primes[i] <= x; i++) {
> if (!(x % primes[i])) {
> return false;
> }
> }
> }
> return true;
> }

It's not possible in all cases. Also, the tension is not always just
between a natural loop condition and having a signal exit. Let me
illustrate this with the primes example.

If you add a sentinel of 1 at the end of the primes array you can write
the test like this:

unsigned i = 0;
while (primes[i] * primes[i] <= x && x % primes[i])
++i;
return x > 1 && primes[i] > 1;

Now this has a simple, natural loop but the single exit is with a not
entirely obvious return value. Is that trade-off worth it? I don't
know for sure.

Alternatively you could add a more logical sentinel -- the next prime
(31627) knowing that no input x will be > 31627*31627. Now you'd write:

unsigned i = 0;
while (primes[i] * primes[i] <= x)
++i;
return x > 1 && i < HOWMANYPRIMES - 1;

Is that any better? Again, I would never be able to say for sure.
Mentally I ascribe to various parts of the program a cost and I try to
find the minimum cost solution. Complex loop conditions have a cost
but, for me, it's lower than the cost of a break. A return from a loop
has lower "yuck" factor than a break plus an extra variable. The costs
aren't fixed and it's all very vague -- largely derived from looking at
code that I've decided I like.

(I am pretty sure there will be an error in one or both of these
examples. I've not spent enough time to be sure of them.)
>
> ?
>
> bye

--
Ben.