C++

Forum

 
Cant understand why this isnt working

BryanTriana (18)
I have a pn_count() function that is supposed to calculate the number of prime numbers under a given parameter. This function works based on the sieve of atkin but it is calculating wrong values. I dont understand what I am doing wrong, can someone enlighten me in making the function pn_count work?


pn_count():
1
2
3
4
5
6
7
8
 
  long long inpalprime::pn_count(long long n)
{
  long long primecount= std::count(atkinsieve(n).begin(), atkinsieve(n).end(), true);
    
    
    
    return primecount;
}


sieve of atkin:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
 
std::vector<bool> inpalprime::atkinsieve(long long m)
{
    std::vector<bool> p_test(m+1, false);
    
    //defines square root of m
    long long root=ceil(sqrt(m));
    
    //sieve axioms
    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<=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;
}
helios (17575)
std::count() doesn't work if its first and second parameters are not iterators into the same sequence. Your pn_count() also has the issue that it's uselessly computing the sieve twice.
1
2
3
4
5
6
 
long long inpalprime::pn_count(long long n)
{
  auto p = atkinsieve(n);
  long long primecount= std::count(p.begin(), p.end(), true);
  return primecount;
}

I haven't looked at the rest of your code.
Last edited on
BryanTriana (18)
ok the pn_count function worked like this before:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
 long long inpalprime::pn_count(long long n)
{
    //counts the number of primes less or equal to n
    for(std::vector<bool>::size_type it=atkinsieve(n).size()-1; it!=1; it--)
    {
        if(atkinsieve(n)[it])
        {
            primecount++;
        }
    }
    
    
    return primecount;
}


but if I do it this way it is very inefficient for calculating the number of primes under a given number, does anyone know a way to make this efficient?
ne555 (10692)
Every time that you call atkinsieve() the function will execute.
That function is quite costly.

Call it once and save the returned value, then work on that.
Last edited on
Topic archived. No new replies allowed.