Trouble returning a value from a vector(prime number generation)

[BryanTriana]

I am trying to make a c++ library for prime numbers; the first function I want to create is a prime number generator. I decided to use the sieve of atkin because of the good efficiency it offers. I also wanted to use vectors for the sieve because they were a new topic I was recently learning, but currently I am having trouble with returning a value from the vector.

Header file:

  #ifndef inpalprime_hpp
#define inpalprime_hpp

#include <stdio.h>
#include <vector>

class inpalprime
{
public:
    long long p_gen(long long n);
    
    
private:
    
};


#endif /* inpalprime_hpp */

cpp file:

#include "inpalprime.hpp"
#include <cmath>


long long inpalprime::p_gen(long long n)
{
   
    std::vector<bool> p_test (n, false);
    long long root= ceil(sqrt(n));
    
    //Sieve of atkin
    for(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<n && (i%12==1 || i%12==5))
            {
                p_test[i].flip();
            }
            i=(3*x*x)+(y*y);
            if(i<n && n%12==7)
            {
                p_test[i].flip();
            }
            i=(3*x*x)-(y*y);
            if(x>y && i<n && i%12==11)
            {
                p_test[i].flip();
            }
        }
    }
    p_test[2]=p_test[3]=p_test[5]=p_test[7]=true;
    
    for(long long r=5; r<=root; r++)
    {
        if(bool(p_test[r]))
        {
            for(long long j=r*r; j<n; j+=r*r)
            {
                p_test[j]=false;
            }
        }
    }
    
    std::vector<long long> p_list;
    for(std::vector<bool>::size_type a=1; a!=p_test.size(); a++)
    {
        if(bool(p_test[a]))
           {
               p_list.push_back(a);
           }
    }

    
    return p_list.back();
}

example with main():

/#include <iostream>
#include <vector>
#include "inpalprime.hpp"


int main(int argc, const char * argv[])
{
    inpalprime obj;
    for(long long i=2; i<100; i++)
    {
        std::cout << obj.p_gen(i) << std::endl;
    }
}

If you compile it there will be an error marking the return statement in the function in .cpp file. Can someone tell me how to fix this or if there is a better way to implement the sieve of atkin using vectors. I dont want to create an output inside the p_gen function but I would like to know a good way of outputting the last prime number in the range assigned by the user(the parameter n in p_gen(n))

[MZH]

Add the following lines before return p_list.back().

std::cout << "n = " << n << std::endl;
std::cout << "p_test.size() " << p_test.size() << std::endl;
std::cout << "p_list.size() " << p_list.size() << std::endl;

Then, work backwards to figure out where the problem is.

[BryanTriana]

Ok I tried that with n=100 and it gave me the following results:
n= 100
p_list= 20
p_test= 100

code:

int main(int argc, const char * argv[])
{
    inpalprime obj;
    obj.p_gen(100);
}

[MZH]

The problem occurs when n = 2.

[BryanTriana]

Thanks a lot MZH I fixed it by adding the following code to the cpp file:

 if(n==2)
    {
        return 2;
    }

not sure if it is a good fix but it seems to be working.

[MZH]

I should have said, "One problem occurs at n = 2." This line:
p_test[2]=p_test[3]=p_test[5]=p_test[7]=true;
will cause problems for small values of n because you are assigning values past the end of the vector. This is undefined behavior and will cause mysterious problems in the future.

My biggest problem with this function is that it's not clear what it does. Does it return the largest prime less than or equal to n? Add comments to explain to others (and your future self) what this function does and what it returns.

Other notes:
- p_test contains bools, so you don't need to cast to bool in conditionals (if(), while(), etc.).
- at the end of p_gen(), you only care about the last number added. Don't create a vector to store all the previous values. Just have a long long variable that holds the last number found.
- The inpalprime class serves no purpose. Not everything needs to be a class in C++. p_gen() should be a free-standing function. (I'm guessing you've learned Java before.)
- The stdio.h include is not needed. If you did need it, it should be called cstdio.

[BryanTriana]

Ok I did the fixes that you told me, I created a class because I want to have multiple functions
that are related to prime numbers. The objective of the first function is to find the highest possible prime under a number 'n' specified by the user.

Here is the new code:

Header:

#ifndef inpalprime_hpp
#define inpalprime_hpp

class inpalprime
{

public:
    long long p_gen(long long n);
    
private:
    long long prime=0;
    
};

#endif /* inpalprime_hpp */ 

cpp file:

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


long long inpalprime::p_gen(long long n)
{
    //return values to deal with values of n less than 7
   switch(n)
    {
        case 2:return 2;
        case 3:return 3;
        case 5:return 5;
        case 7:return 7;
    }
    //stores boolean values for primality testing, 1: prime, 0: not prime
    std::vector<bool> p_test (n, false);
    long long root= ceil(sqrt(n));
    
    //sieve of atkin
    for(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<n && (i%12==1 || i%12==5))
            {
                p_test[i].flip();
            }
            i=(3*x*x)+(y*y);
            if(i<n && n%12==7)
            {
                p_test[i].flip();
            }
            i=(3*x*x)-(y*y);
            if(x>y && i<n && 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(bool(p_test[r]))
        {
            for(long long j=r*r; j<n; j+=r*r)
            {
                p_test[j]=false;
            }
        }
    }
    
    //finds the highest possible prime under n
    for(std::vector<bool>::size_type a=1; a!=p_test.size(); a++)
    {
        if((p_test[a]))
           {
               prime=a;
           }
    }

    
    return prime;
}

[MZH]

This looks much better. It's much easier to follow the code now.

I'm unclear on one aspect. Should this function return a prime number less than n, or less than or equal to n? In other words, should inpalprime(13) return 13 or 11? The p_test vector only stores values up to n-1 (the indices of a size n vector go from 0 to n-1), so the final return will always be less than n. But, the first switch statement returns a number equal to n if n is prime and less than or equal to 7.

Also, your program will still crash if you call ispalprime(6) or any composite number less than 7. You need to handle the composite numbers below 7 in the initial switch.

Finally, an easy optimization:
in the final loop here:

    //finds the highest possible prime under n
    for(std::vector<bool>::size_type a=1; a!=p_test.size(); a++)
    {
        if((p_test[a]))
           {
               prime=a;
           }
    }
    return prime;

Why not start at the end of the p_test, search backwards and return the first value where p_test[a] is true? This way, you don't have to search through the entire vector.

[BryanTriana]

Thanks for the optimization, now it looks like this:

 //finds the highest possible prime under n
    for(std::vector<bool>::size_type a=p_test.size()-1; a!=1; a--)
    {
        if((p_test[a]))
           {
               prime=a;
               break;
           }
    }

I would like to return the prime number equal or less to n but now I realize I dont know how to do that with the current algorithm that uses vectors.

[MZH]

I think that replacing each n in the function with n+1 (except for the switch block) should work. That would need testing, though.

Also, this might be a style preference, but I prefer early returns.

    //finds the highest possible prime under n
    for(std::vector<bool>::size_type a=p_test.size()-1; a!=1; a--)
    {
        if((p_test[a]))
           {
               return a;
           }
    }