First Program Bug (Newbie)

[Mensanator]

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