DEV Community

loading...
Cover image for Calculating Prime Numbers with CircleCI

Calculating Prime Numbers with CircleCI

Nick Lavrov
・4 min read

If you're looking for a list of prime numbers, you don't have to look very far. Nevertheless, here's my small, completely useful way to add to this list.

I decided the best way for me to do this was to create a continuously growing list of prime numbers maintained in a Github repo. I would use CircleCI to compute the next prime number and update the list.

GitHub logo NickLavrov / circleci-primes

Create a list of prime numbers using CircleCI

circleci-primes

CircleCI

Create a list of prime numbers using CircleCI!

This repo keeps a running list of prime numbers, found in primes.txt. A commit to the master branch triggers a build on CircleCI, calculates the next prime number, adds it to the list, commits the new list to the master branch, triggers a build on CircleCI, calculates the next prime number, adds it to the list... you get the idea.

Watch the builds here!




The structure of the repo is simple enough. There is a list of primes, initialized with 2 and 3; a script called nextprime.sh that, unsurprisingly, finds the next prime; and a CircleCI config file that appends the next prime to the list and commits the new list.

Here's the fun part - builds on CircleCI are triggered by commits to the master branch, and since the build commits the new prime list to the master branch, a new build will calculate the next prime number. Watch the builds in real time here! This will happen until I cancel a build before the commit happens, or until the kind folks at CircleCI decide enough is enough.

Are there better, faster ways to do this? Of course. Is this a complete waste of time? Debatable. When you constrain yourself to a certain set of tools, you're forced to come up with creative solutions. Because of this, I learned some new things about shell scripting and about how CircleCI handles SSH and Github communications.

If you're interested, below are some of the challenges I faced:

• Doing math with shell scripts

I decided I wanted to use a shell script for two main reasons. Firstly, I wanted to use the tiny Docker alpine image for my builds. I don't want any extra stuff! (Although you'll see below that I needed to add the bc (Basic Calculator) tool anyway) Secondly, I love shell scripting. Yeah, I'm serious.

I was originally using expr to do math, but after trial and error, I realized that there was an upper limit to numbers expr could handle. Specifically, from the man page:

Arithmetic operations are performed using signed integer math with a range according to the C intmax_t data type (the largest signed integral type available).

So once I started dealing with numbers greater than 2^63, there would be issues. Try running the following commands in your terminal to see for yourself:

expr 42 + 1
expr 9223372036854775808 + 1

Since I fully expect this to calculate prime numbers past 2^63, this limit of expr is unacceptable.

I found a tool called bc that does not have this limit because it "supports arbitrary precision numbers with interactive execution of statements." It's also easier to use, in my opinion. With a little work after that, my prime number generation script was finished. The nice thing about having a list of prime numbers is that when finding the next prime number, you have a nice list of divisors to test it!

• Pushing to a Github repo with CircleCI

It's easy enough to pull from a Github repo with Circle. Pushing, on the other hand, is a bit harder. One way is to use your own Github token (stored securely as an env var within CircleCI, of course!) to push, with something like this:

git push -q https://${GITHUB_TOKEN}@github.com/NickLavrov/circleci-primes.git HEAD

But I didn't want to go that route. I wanted to push on behalf of CircleCI and not have any risk of exposing my personal Github token (that -q is very, very important).

So I created a new deploy key for the repo on Github, gave it write access, added the SSH key on CircleCI, and thought I was done. Unfortunately, when it came time to push, I was hit with:

/bin/sh: git: not found

So I installed git. Then I was hit with:

fatal: You are not currently on a branch.

So I changed the command to git push origin HEAD:master and was hit with:

fatal: cannot run ssh: No such file or directory

So I added a step to install openssh and was hit with:

The authenticity of host 'github.com (192.30.253.112)' can't be established.

This is where I found a solution that I really don't like. I added a step in the config to add github.com to the ~/.ssh/known_hosts file like this:

echo '
github.com ssh-rsa AAAAB3NzaC1yc2EAAAABIwAAAQEAq2A7hRGmdnm9tUDbO9IDSwBK6TbQa+PXYPCPy6rbTrTtw7PHkccKrpp0yVhp5HdEIcKr6pLlVDBfOLX9QUsyCOV0wzfjIJNlGEYsdlLJizHhbn2mUjvSAHQqZETYP81eFzLQNnPHt4EVVUh7VfDESU84KezmD5QlWpXLmvU31/yMf+Se8xhHTvKSCZIFImWwoG6mbUoWf9nzpIoaSjB+weqqUUmpaaasXVal72J+UX2B+2RPW3RcT0eOzQgqlJL3RKrTJvdsjE3JEAvGq3lGHSZXy28G3skua2SmVi/w4yCE6gbODqnTWlg7+wC604ydGXA8VJiS5ap43JXiUFFAaQ==
' >> ~/.ssh/known_hosts
Enter fullscreen mode Exit fullscreen mode

I didn't want to install any other tools besides bc, git, and openssh, so I stayed with this solution. If you can think of something a bit more elegant, I'd love to know!

Discussion (3)

Collapse
0xyasser profile image
Yasser A • Edited

Interesting!
I'm wondering if you are going to reach the limit of CircleCI builds if you use the free account.
I would recommend filling the list with the first 10 or 100 million primes at least then let it run.
you could do that easily with a python script using the below code. it won't take that long at all

def primes_sieve(limit):
    limitn = limit+1
    not_prime = [False] * limitn
    primes = []

    for i in range(2, limitn):
        if not_prime[i]:
            continue
        for f in range(i*2, limitn, i):
            not_prime[f] = True

        primes.append(i)

    return primes
print(primes_sieve(10000000))

Collapse
nicklavrov profile image
Nick Lavrov Author

Ah, according to their pricing plan here, I get 1500 minutes of build time per month for free. So the build will fail once it hits that limit, I suppose.

Collapse
nicklavrov profile image
Nick Lavrov Author

Update: