Ayuto

Edges of a Hasse-diagram

Nov 18th, 2013
204
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.70 KB | None | 0 0
  1. def isPrime(n):
  2.     '''
  3.    Returns True if the given number is a prime.
  4.    '''
  5.  
  6.     for x in xrange(2, n):
  7.         if n % x == 0:
  8.             return False
  9.  
  10.     return True
  11.  
  12. def getPrimes(n):
  13.     '''
  14.    Returns all primes until <n> as a generator.
  15.    '''
  16.  
  17.     return (x for x in xrange(2, n+1) if isPrime(x))
  18.  
  19. def getEdges(n):
  20.     '''
  21.    Returns the count of all edges within a Hasse-diagram until <n>.
  22.    '''
  23.  
  24.     count  = 0
  25.     primes = tuple(getPrimes(n))
  26.  
  27.     for x in xrange(1, n+1):
  28.         for divisor in primes:
  29.             if divisor > x:
  30.                 break
  31.  
  32.             if x % divisor == 0:
  33.                 count += 1
  34.  
  35.     return count
  36.  
  37.  
  38. print getEdges(5000)
Advertisement
Add Comment
Please, Sign In to add comment