Skip to content

Marina Mele's site

Reflections on family, values, and personal growth

Menu
  • Home
  • About
Menu

Python scripts for prime numbers and divisors

Posted on December 7, 2013September 26, 2014 by Marina Mele

Very recently I been interested in solving the problems proposed by Project Euler. Currently I just solved about 20 problems, but I run into some nice algorithms for finding prime numbers and divisors that I would like to share.

This first snippet defines a Python function that returns a list of the prime numbers up to a given integer. It uses the Sieve of Atkin, which is a modern algorithm that optimizes the Sieve of Eratosthenes.


File: marinamele_sieve_atkin.py
-------------------------------

import math
def atkin(nmax):
    """
    Returns a list of prime numbers below the number "nmax"
    """
    is_prime = dict([(i, False) for i in range(5, nmax+1)])
    for x in range(1, int(math.sqrt(nmax))+1):
        for y in range(1, int(math.sqrt(nmax))+1):
            n = 4*x**2 + y**2
            if (n <= nmax) and ((n % 12 == 1) or (n % 12 == 5)):
                is_prime[n] = not is_prime[n]
            n = 3*x**2 + y**2
            if (n <= nmax) and (n % 12 == 7):
                is_prime[n] = not is_prime[n]
            n = 3*x**2 - y**2
            if (x > y) and (n <= nmax) and (n % 12 == 11):
                is_prime[n] = not is_prime[n]
    for n in range(5, int(math.sqrt(nmax))+1):
        if is_prime[n]:
            ik = 1
            while (ik * n**2 <= nmax):
                is_prime[ik * n**2] = False
                ik += 1
    primes = []
    for i in range(nmax + 1):
        if i in [0, 1, 4]: pass
        elif i in [2,3] or is_prime[i]: primes.append(i)
        else: pass
    return primes
assert(atkin(30)==[2, 3, 5, 7, 11, 13, 17, 19, 23, 29])

This other snippet returns an unsorted list of all the divisors of a given integer. It has a second argument which is a list of prime numbers. Note that this list can be found using the previous atkin function.


File: marinamele_getDivisors.py
-------------------------------

def getDivisors(number, primes):
    """
    Returns an unsorted list of the divisors of 'number' using the list of prime numbers 'primes'
    """
    if number == 1: return [number,]
    if number in primes:
        return [1, number]
    divisors = []
    for p in primes:
        if number % p == 0:
            k = 1
            pdiv = []
            while (p**k < number) and (number % (p**k)) == 0:
                pdiv.append(p**k)
                k += 1
            divisors_copy = divisors[:]
            for p in pdiv:
                divisors += [pk*p for pk in divisors_copy if pk*p < number]
            divisors += pdiv
    divisors += [1, number]
    return divisors

Hope it is helpful!

And please, share any thoughts and improvements of the algorithms! 🙂

Marina Melé
Marina Mele

Marina Mele has experience in artificial intelligence implementation and has led tech teams for over a decade. On her personal blog (marinamele.com), she writes about personal growth, family values, AI, and other topics she’s passionate about. Marina also publishes a weekly AI newsletter featuring the latest advancements and innovations in the field (marinamele.substack.com)

Leave a Reply Cancel reply

You must be logged in to post a comment.

Categories

  • Personal Growth and Development
  • Artificial Intelligence
  • Mindful Parenting and Family Life
  • Productivity and Time Management
  • Mindfulness and Wellness
  • Values and Life Lessons
  • Posts en català
  • Other things to learn

Recent Posts

  • BlueSky Social – A Sneak Peek at the Future of Social Media
  • The Incredible Journey of AI Image Generation
  • AI and Fundamental Rights: How the AI Act Aims to Protect Individuals
  • Overcoming Regrets: Finding the Strength to Move Forward
  • Thinking Outside the Box: Creative Problem-Solving with Critical Thinking

RSS

  • Entries RSS
Follow @marina_mele
  • Cookie Policy
  • Privacy Policy
©2023 Marina Mele's site | Built using WordPress and Responsive Blogily theme by Superb
This website uses cookies to improve your experience. If you keep navigating through this website, we'll assume you're ok with this, but you can opt-out if you wish.Accept Read More
Privacy & Cookies Policy

Privacy Overview

This website uses cookies to improve your experience while you navigate through the website. Out of these, the cookies that are categorized as necessary are stored on your browser as they are essential for the working of basic functionalities of the website. We also use third-party cookies that help us analyze and understand how you use this website. These cookies will be stored in your browser only with your consent. You also have the option to opt-out of these cookies. But opting out of some of these cookies may affect your browsing experience.
Necessary
Always Enabled
Necessary cookies are absolutely essential for the website to function properly. This category only includes cookies that ensures basic functionalities and security features of the website. These cookies do not store any personal information.
Non-necessary
Any cookies that may not be particularly necessary for the website to function and is used specifically to collect user personal data via analytics, ads, other embedded contents are termed as non-necessary cookies. It is mandatory to procure user consent prior to running these cookies on your website.
SAVE & ACCEPT