First Program Bug (Newbie)

Tue Mar 18 20:39:15 EDT 2008

On Mar 18, 6:39 pm, oog1e <""benjamin.serrato\"@G(oog1e)MAIL.com">
wrote:
> Hey, big thanks to you and Gabriel for replying. I couldn't quite follow
> what you did yet. What is this 'gimpy' thing

gmpy. It's the GMP (Gnu Multi-Precision) C-library in
a Python wrapper. It supports arbitrary precision integers,
floats and rationals. Although Python has built in Big
Integers, the gmpy versions can sometimes run rings around
Python's. Also, lots of functions unavailable elswhere.

> and where can I read about it?

http://code.google.com/p/gmpy

> In response:
>
> First: Heh, I'm a little embarrassed I didn't notice this. I thought 'I
> only need to check up to half' but it didn't occur that base**2 was more
> than 1/2 candidate.
>
> Second: I don't quite follow this.

Actually, I'm not following it anymore either. For a while my
test program was claiming 27 was prime. All these false primes
had 0 as the remainder of candidate/2. I put this in to reject
them, but I don't see the problem anymore.

>
> Third: Yeah, I found that bug just before, and because of, posting.
>
> Fourth: I used the incrementing command and incremented candidates by
> two to check only odds and now the program is a lot faster.
>
> Thanks a lot for yall's replies. Three more things before I go. What is
> the square root function in python?

There's one in the math module. Use the one in gmpy if you have it.

> I couldn't find the fact.py demo
> script. I didn't mean return I meant 'continue'.
>
>
>
> Mensanator wrote:
> > On Mar 17, 7:03 pm, Benjamin Serrato <benjamin.serr... at gmail.com>
> > wrote:
> >> I Found It!! The following was a post asking for help finding a bug. I
> >> thought I needed help with my syntax, but just before sending I found
> >> the bug on line 13. Line 13 should read: "base = 2". I would still
> >> appreciate any comments on my program. Maybe there is a better way to do
> >> it that I didn't think about. I know it's not that interesting but it's
> >> my first one.
>
> >> [post]
> >> I'm almost halfway through an online tutorial I found on the python.org
> >> site and decided to stop and write a program for myself. I got it in my
> >> head to write a program to print all the primes; the idea came from
> >> another tutorial. The program prints some non-prime numbers. In a
> >> comparison to lists of primes the program prints eight non-primes for
> >> numbers less than 150. Those numbers are [27,35,87,95,119,123,143,147].
> >> Here is the program.
>
> >> base = 2
> >> candidate = 3
>
> >> while True:
> >>         while candidate % base != 0:
> >>                 base = base + 1
> >>                 if base > (candidate / 2):
> >>                         print candidate
> >>                         candidate = candidate + 1
> >>                         base = 2
> >>         else:
> >>                 candidate = candidate + 1
>
> >> The following is a rundown of the program.
>
> >> candidate: A possible prime number.
> >> base: Start point for divisibility testing.
> >> outer while loop: Causes the program to loop.
> >> inner while loop: Obviously, checks if 'candidate' mod 'base' equals
> >> zero. If not base is incremented by one then 'if loop'.
> >> if loop: After base has been incremented this checks whether all the
> >> possible divisors have been used up. If they have then 'candidate' must
> >> be prime. So, candidate is printed, a new candidate is chosen and the
> >> base is reset.
> >> else loop: If 'candidate' mod 'base' equals zero, then 'candidate' is
> >> not prime and a new candidate is chosen.
>
> >> I realize yall probably didn't need all that.
>
> >> At first I tried to use 'return' on the 'else' block to cause the
> >> program to loop, but I don't understand 'return' yet and that didn't
> >> work. So, I put the rest into another while loop and was really happy to
> >> find it worked but the program prints some non-prime numbers.
>
> >> Thanks, Benjamin Serrato
>
> >> P.S. What is the chance I'll get spam for using my real email address? I
> >> currently don't get any so...
> >> [/post]
>
> > Several items.
>
> > First, you don't need to check base larger than sqrt(candidate).
>
> > Second, see comments following dc.
>
> > Third, you need to add base = 2 to end of program, otherwise next
> > candidate starts base where previous candidate left off.
>
> > Fourth, use +=1 to increment.
>
> > Finally, throw this away and use gmpy. :-)
>
> > import gmpy  # for Quality Assurance
> > base = 2
> > candidate = 3
> > p = 0                            # prime count
> > while p<100:                     # limit the loop to 100 primes
> >   while candidate % base != 0:
> >     base += 1
> >     #if base > (candidate / 2):
> >     if base > (gmpy.sqrt(candidate)):  # only need to test to
> > sqrt(candidate)
> >       dc = divmod(candidate,2)         # remainder==0 gives false
> > primes
> >       if dc[1]==1:
> >         #
> >         # the gmpy functions are for QA, verifies that what you call a
> > prime
> >         # really is one and the next_prime makes sure you don't skip
> > any
> >         # these can be removed once working
> >         #
> >         print
> > candidate,gmpy.is_prime(candidate)>0,gmpy.next_prime(candidate)
> >         p += 1
> >         candidate += 1
> >         base = 2
> >       else:
> >         candidate += 1                 # false prime, reset
> >         base = 2
> >   else:
> >     candidate += 1
> >     base = 2                           # failure to reset causes false
> > primes
>
> > ##  3 True 5
> > ##  5 True 7
> > ##  7 True 11
> > ##  11 True 13
> > ##  13 True 17
> > ##  17 True 19
> > ##  19 True 23
> > ##  23 True 29
> > ##  29 True 31
> > ##  31 True 37
> > ##  37 True 41
> > ##  41 True 43
> > ##  43 True 47
> > ##  47 True 53
> > ##  53 True 59
> > ##  59 True 61
> > ##  61 True 67
> > ##  67 True 71
> > ##  71 True 73
> > ##  73 True 79
> > ##  79 True 83
> > ##  83 True 89
> > ##  89 True 97
> > ##  97 True 101
> > ##  101 True 103
> > ##  103 True 107
> > ##  107 True 109
> > ##  109 True 113
> > ##  113 True 127
> > ##  127 True 131
> > ##  131 True 137
> > ##  137 True 139
> > ##  139 True 149
> > ##  149 True 151
> > ##  151 True 157
> > ##  157 True 163
> > ##  163 True 167
> > ##  167 True 173
> > ##  173 True 179
> > ##  179 True 181
> > ##  181 True 191
> > ##  191 True 193
> > ##  193 True 197
> > ##  197 True 199
> > ##  199 True 211
> > ##  211 True 223
> > ##  223 True 227
> > ##  227 True 229
> > ##  229 True 233
> > ##  233 True 239
> > ##  239 True 241
> > ##  241 True 251
> > ##  251 True 257
> > ##  257 True 263
> > ##  263 True 269
> > ##  269 True 271
> > ##  271 True 277
> > ##  277 True 281
> > ##  281 True 283
> > ##  283 True 293
> > ##  293 True 307
> > ##  307 True 311
> > ##  311 True 313
> > ##  313 True 317
> > ##  317 True 331
> > ##  331 True 337
> > ##  337 True 347
> > ##  347 True 349
> > ##  349 True 353
> > ##  353 True 359
> > ##  359 True 367
> > ##  367 True 373
> > ##  373 True 379
> > ##  379 True 383
> > ##  383 True 389
> > ##  389 True 397
> > ##  397 True 401
> > ##  401 True 409
> > ##  409 True 419
> > ##  419 True 421
> > ##  421 True 431
> > ##  431 True 433
> > ##  433 True 439
> > ##  439 True 443
> > ##  443 True 449
> > ##  449 True 457
> > ##  457 True 461
> > ##  461 True 463
> > ##  463 True 467
> > ##  467 True 479
> > ##  479 True 487
> > ##  487 True 491
> > ##  491 True 499
> > ##  499 True 503
> > ##  503 True 509
> > ##  509 True 521
> > ##  521 True 523
> > ##  523 True 541
> > ##  541 True 547
> > ##  547 True 557