2
\$\begingroup\$

This prime number library is one of my first programming projects I've done in c++. My goal is to create useful functions that deal with prime numbers in an efficient way.Note: (Most of the functions used are powered by the sieve of Atkin)

I'd like to know any sort of optimization or better code practices that I should change or incorporate to my project, any help is greatly appreciated.

functions:

  • pn_find(n): Finds the highest prime number less or equal to the input given.

  • pn_count(n): Counts the amount of primes under a given number(including n).

  • pn_den(h): Calculates the density of prime numbers from 1 to h.

  • pn_test(a): Primality test for a number, returns a boolean value(1 if prime and 0 if not prime).

  • pn_twin(a): Tests if a given number is a twin prime, returns a boolean value(1 if it is twin prime and 0 if it is not twin prime).

  • pn_cousin(a): Tests if a given number is a cousin prime, returns a boolean value(1 if it is a cousin prime and 0 if it is not a cousin prime).

  • pn_sexy(a): Tests if a given number is a sexy prime, returns a boolean value(1 if it is a sexy prime and 0 if it is not a sexy prime).

  • pn_pal(n): Finds the highest palindromic prime equal or less than n.

  • n_fac(f): Finds the highest prime factor of a given number.

  • n_cfac(f): Counts the number of prime factors that composes a number(including f).

hpp file:

    #ifndef inpalprime_hpp
    #define inpalprime_hpp

    #include <vector>
    #include <string>


    class inpalprime
    {

    public:
    long long pn_find(long long n);
    long long pn_count(long long n);
    long double pn_den(long double h);
    bool pn_test(long long a);
    bool pn_twin(long long a);
    bool pn_cousin(long long a);
    bool pn_sexy(long long a);
    long long pn_pal(long long n);
    long long n_fac(long long f);
    long long n_cfac(long long f);

private:
    std::vector<bool> atkinsieve(long long m);
    std::vector<long long> factorizer(long long f);
    bool pal_test(long long n);
    long long maxprime;
    long long primecount;
    long double primeden;
    long long pal;
    std::string rev;
    long long maxfac;
    long long cfac;

};


#endif /* inpalprime_hpp */

cpp file:

#include "inpalprime.hpp"
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>


long long inpalprime::pn_find(long long n)
{
    auto p_find=atkinsieve(n);

    //finds the highest possible prime less or equal to n
    for(std::vector<bool>::size_type it=p_find.size(); it!=1; it--)
    {
        if(p_find[it])
        {
            maxprime=it;
            break;
        }
    }


    return maxprime;
}



long long inpalprime::pn_count(long long n)
{
    auto p_count=atkinsieve(n);

    //counts the number of primes less or equal to n
    primecount=std::count(p_count.begin(), p_count.end(), true);


    return primecount;
}



long double inpalprime::pn_den(long double h)
{
    //calculates density of primes from 1 to  h
    primeden=(pn_count(h)/h);


    return primeden;
}



bool inpalprime::pn_test(long long a)
{
    //primality test based on the sieve of atkin
    if(a!=pn_find(a))
    {
        return false;
    }


    return true;
}



bool inpalprime::pn_twin(long long a)
{
    auto p_tw=atkinsieve(a+2);

    if(a==2)
    {
        return false;
    }

    //checks if a+2 or a-2 is also prime
    else if(p_tw[p_tw.size()-3] && (p_tw[p_tw.size()-1] || p_tw[p_tw.size()-5]))
    {
        return true;
    }


    return false;
}



bool inpalprime::pn_cousin(long long a)
{
   auto p_co=atkinsieve(a+4);

    if(a==2)
    {
        return false;
    }

    //checks if a+4 or a-4 is also prime
    else if(p_co[p_co.size()-5] && (p_co[p_co.size()-1] || p_co[p_co.size()-9]))
    {
        return true;
    }


    return false;
}



bool inpalprime::pn_sexy(long long a)
{
    auto p_se=atkinsieve(a+6);

    if(a==2 || a==3)
    {
        return false;
    }

    //checks if a+6 or a-6 is also prime
    else if(p_se[p_se.size()-7] && (p_se[p_se.size()-1] || p_se[p_se.size()-13]))
    {
        return true;
    }


    return false;
}



long long inpalprime::pn_pal(long long n)
{
    auto p_pal=atkinsieve(n);

    //finds the highest palindromic prime less or equal to n
    for(std::vector<bool>::size_type it=p_pal.size(); it!=1; it--)
    {
        if(p_pal[it] && pal_test(it))
        {
            pal=it;
            break;
        }
    }


    return pal;
}



long long inpalprime::n_fac(long long f)
{
    //finds the highest prime factor less or equal to f
    maxfac=factorizer(f).back();


    return maxfac;
}



long long inpalprime::n_cfac(long long f)
{
    //counts the number of prime factors that compose f, if f is prime the returned value is 1
    cfac=factorizer(f).size();


    return cfac;
}



std::vector<bool> inpalprime::atkinsieve(long long m)
{
    std::vector<bool> p_test(m+1, false);

    //defines square root of m
    unsigned long long root=ceil(sqrt(m));

    //sieve axioms
    for(unsigned long long x=1; x<=root; x++)
    {
        for(long long y=1; y<=root; y++)
        {
            long long i=(4*x*x)+(y*y);
            if (i<=m && (i%12==1 || i%12==5))
            {
                p_test[i].flip();
            }
            i=(3*x*x)+(y*y);
            if(i<=m && i%12==7)
            {
                p_test[i].flip();
            }
            i=(3*x*x)-(y*y);
            if(x>y && i<=m && i%12==11)
            {
                p_test[i].flip();
            }
        }
    }

    //marks 2,3,5 and 7 as prime numbers
    p_test[2]=p_test[3]=p_test[5]=p_test[7]=true;

    //marks all multiples of primes as non primes
    for(long long r=5; r<=root; r++)
    {
        if((p_test[r]))
        {
            for(long long j=r*r; j<=m; j+=r*r)
            {
                p_test[j]=false;
            }
        }
    }


    return p_test;
}


std::vector<long long> inpalprime::factorizer(long long f)
{
    std::vector<long long> p_fac;
    long long p=3;

    //removes factors of 2
    while(f%2==0)
    {
        p_fac.push_back(2);
        f=f/2;
    }

    //finds prime factors of f
    while(f!=1)
    {
        while(f%p==0)
        {
            p_fac.push_back(p);
            f=f/p;
        }
        p+=2;
    }


    return p_fac;
}



bool inpalprime::pal_test(long long n)
{
    //converts n to a string
    rev=std::to_string(n);

    //checks if the reverse of rev is equal to rev
    for(int i=0; i<rev.size()/2; i++)
    {
        if(rev[i]!=rev[rev.size()-1-i])
        {
            return false;
        }
    }


    return true;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Dannnno has lots of good comments. In terms of optimizations, this is the sort of thing that never really ends. After some of the obvious things like removing redundant work, using better algorithms will help. SoE is much faster than SoA. There are much faster primality tests vs. generating primes, similarly with counting. The clusters (twin,sexy,etc.) only appear in some remainders modulo a primorial so can be optimized. Once past tiny sizes, there are much faster factoring methods than trial division. \$\endgroup\$ – DanaJ Jul 22 '16 at 20:43
3
\$\begingroup\$

First of all, your formatting is pretty strange. Not sure if thats what your code looks like or if it is just an artefact of the copy-paste, but either way you should clean it up.

Secondly, anytime I see prefixes like pn_*** in C++ I cringe. I could stand it in C, because sometimes there isn't anything else you can do to avoid collisions. But in C++ we have both classes and namespaces, and using one or the other should make it unnecessary to do it. In this case I don't really see a reason to use a class (why should I have to make a new inpalprime in order to do these methods?) so either make everything static, or use a namespace. I'm going to opt for a namespace.

Third, your names are terrible. They're really hard to understand as is. I renamed them like so

pn_find -> largest_prime
pn_count -> count_primes
pn_den -> prime_density
pn_test -> is_prime
pn_twin -> is_twin_prime
pn_cousin -> is_cousin_prime
pn_sexy -> is_sexy_prime
pn_pal -> largest_palindromic_prime
n_fac -> largest_prime_factor
n_cfac -> count_prime_factors
atkinsieve -> get_primes
factorizer -> get_prime_factors
pal_test -> is_palindrome

To me at least, most of these are huge improvements in readability, and some of them are at least a little better.

State

I don't really see why a lot of these share so much state - it makes it hard to read, and there isn't an obvious reason for it. Some of them also don't get appropriately initialized either, which could lead to some surprising behavior.

pn_find (largest_prime)

Just use iterators here, and return instead of breaking. It'll make things much easier. After that, it becomes trivial to use find instead. It is unclear what should have been returned in the error case (i.e. if no prime was found) so I just let it dereference end. Not ideal, but just make sure you specify that using an invalid n is undefined behavior. Otherwise, you could add a check to return some default if n is invalid.

pn_test (is_prime)

You can simplify here a lot. Just invert the comparison (!= to ==) then return the result.

pn_twin, pn_cousin, pn_sexy (is_twin_prime, is_cousin_prime, is_sexy_prime)

Just add all of your booleans together and return the result. Much cleaner.

Beyond that, your implementations of the different calculations don't seem horrid. What is likely to really slow you down is that you recalculate all of your primes, every single time. Same for factors. If you add some sort of caching/memoization (or an improved algorithm) to those two functions then you'll do much better. Additionally, using push_back on vectors is pretty bad - you'll be mallocing out the wazoo which will slow things down pretty quickly. Try to reserve enough space to begin with (which is hard, but you might be able to come up with a decent metric) and then your push backs won't malloc anything until they fill up your vector. Your is_palindrome function could be easily threaded for a slight speed gain there.

This is what I came up with at the end

inpalprime.hpp

#ifndef inpalprime_hpp
#define inpalprime_hpp

#include <vector>
#include <string>

namespace inpalprime {
    std::vector<bool> get_primes(long long m);


    std::vector<long long> get_prime_factors(long long f);
    bool is_palindrome(long long n);

    long long largest_prime(long long n);

    long long count_primes(long long n);

    long double prime_density(long double h);

    bool is_prime(long long p);

    bool is_twin_prime(long long p);

    bool is_cousin_prime(long long p);

    bool is_sexy_prime(long long p);

    long long largest_palindromic_prime(long long n);

    long long largest_prime_factor(long long f);

    long long count_prime_factors(long long f);
}

#endif // defined inpalprime_hpp

inpalprime.cpp

#include "inpalprime.hpp"
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>


long long inpalprime::largest_prime(long long n)
{
    auto primes = get_primes(n);
    auto it = std::find(primes.rbegin(), primes.rend(), true);
    return primes.size() - std::distance(primes.rbegin(), it);
}

long long inpalprime::count_primes(long long n)
{
    auto primes = get_primes(n);
    return std::count(primes.begin(), primes.end(), true);
}

long double inpalprime::prime_density(long double h)
{
    return count_primes(h) / h;
}

bool inpalprime::is_prime(long long a)
{
    return a == largest_prime(a);
}

bool inpalprime::is_twin_prime(long long a)
{
    auto primes = get_primes(a + 2);

    return a != 2
           && primes[primes.size()-3]
           && (primes[primes.size()-1] || primes[primes.size()-5]);
}

bool inpalprime::is_cousin_prime(long long a)
{
    auto primes = get_primes(a + 4);

    return a != 2
            && primes[primes.size()-5]
            && (primes[primes.size()-1] || primes[primes.size()-9]);
}

bool inpalprime::is_sexy_prime(long long a)
{
    auto primes = get_primes(a + 6);

    return (a != 2 && a != 3)
        && primes[primes.size() - 7]
        && (primes[primes.size() - 1] || primes[primes.size() - 13]);
}

long long inpalprime::largest_palindromic_prime(long long n)
{
    auto primes = get_primes(n);

    auto it = std::find_if(primes.rbegin(), primes.rend(), [&](auto it) {
        auto num = primes.size() - std::distance(primes.rbegin(), it)
        return *it && is_palindrome(num);
    });
    return primes.size() - std::distance(primes.rbegin(), it);
}

long long inpalprime::largest_prime_factor(long long f)
{
    return get_prime_factors(f).back();
}

long long inpalprime::count_prime_factors(long long f)
{
    return get_prime_factors(f).size();
}

std::vector<bool> inpalprime::get_primes(long long m)
{
    std::vector<bool> p_test(m+1, false);

    //defines square root of m
    unsigned long long root=ceil(sqrt(m));

    //sieve axioms
    for(unsigned long long x=1; x<=root; x++)
    {
        for(long long y=1; y<=root; y++)
        {
            long long i=(4*x*x)+(y*y);
            if (i<=m && (i%12==1 || i%12==5))
            {
                p_test[i].flip();
            }
            i=(3*x*x)+(y*y);
            if(i<=m && i%12==7)
            {
                p_test[i].flip();
            }
            i=(3*x*x)-(y*y);
            if(x>y && i<=m && i%12==11)
            {
                p_test[i].flip();
            }
        }
    }

    //marks 2,3,5 and 7 as prime numbers
    p_test[2]=p_test[3]=p_test[5]=p_test[7]=true;

    //marks all multiples of primes as non primes
    for(long long r=5; r<=root; r++)
    {
        if((p_test[r]))
        {
            for(long long j=r*r; j<=m; j+=r*r)
            {
                p_test[j]=false;
            }
        }
    }

    return p_test;
}


std::vector<long long> inpalprime::get_prime_factors(long long f)
{
    std::vector<long long> p_fac;
    long long p=3;

    //removes factors of 2
    while(f%2==0)
    {
        p_fac.push_back(2);
        f=f/2;
    }

    //finds prime factors of f
    while(f!=1)
    {
        while(f%p==0)
        {
            p_fac.push_back(p);
            f=f/p;
        }
        p+=2;
    }

    return p_fac;
}

bool inpalprime::is_palindrome(long long n)
{
    //converts n to a string
    std::string rev = std::to_string(n);

    //checks if the reverse of rev is equal to rev
    for(int i=0; i<rev.size()/2; i++)
    {
        if(rev[i]!=rev[rev.size()-1-i])
        {
            return false;
        }
    }
    return true;
}
\$\endgroup\$
  • \$\begingroup\$ I am having issues with the largest_palindromic_prime() function, the compiler is telling me that auto is not allowed in a lambda parameter. I am not used to working with lambdas so I am a little bit lost in that part, what can I do to fix the following line: auto it = std::find_if(primes.rbegin(), primes.rend(), [&](auto it) { auto num = primes.size() - std::distance(primes.rbegin(), it) \$\endgroup\$ – InversePalindrome Jul 1 '16 at 4:01
  • \$\begingroup\$ @InversePalindrome its certainly possible that parts of this aren't exactly correct - I didn't have a compiler on the machine I wrote this code on. Change it to not use auto - either specify the type, or you could probably make it work with decltype. \$\endgroup\$ – Dannnno Jul 1 '16 at 4:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.