title: Speed up a search for Carmichael numbers?
body: <p>The main question here is: is there a better way that using "all" in Python?
  I have read that it goes through every condition and then comes back to see if any are true. I want to check one condition at a time and then quit as soon as one doesn't work. I believe this is called "Short Circuit.....". I can't use a series of "and"s because they change by input and there could be millions of conditions.</p>
  
  <p>I'm looking for <a href="https://en.wikipedia.org/wiki/Carmichael_number" rel="nofollow noreferrer">Carmichael numbers</a>. One definition for a Carmichael Number is that b^n = b (mod n) for all 1 &lt; b &lt; n. If a number n fails the test then it's composite. If it passes the test it may be either prime or Carmichael. I then checked if it was prime or not.</p>
  
  <p>I used the code:</p>
  
  <pre><code>def Carm(num):
      if all(gcd(k,num) == 1 for k in range(3,int(round(num**0.5)),2)) and gcd(2,num) == 1:
          print(num,'is a Prime Number')
      elif all(pow(b,num,num)==b for b in range(1,num)) and gcd(num,2)==1:
          print(num,'is a Carmichael Number')
      else:
          print(num,'is not a Carmichael Number')
  </code></pre>