C++

Forum

 
Help with counting primes from 1 to n

nero1010 (7)
This is what I have so far but its not printing out the correct answers. I'm trying to get it to print the number of primes. The rest of my code works fine but this part I just can't get. 

1
2
3
4
5
6
7
8
9
10
11
12
13
 
 unsigned long long pi(unsigned long long n)
{
    for(int i=1; i<sqrt(n); ++i)
    {
        if(isprime(i)==true)
        {
            for(int j=i*i; j<n; j+=i*i)
            {
                isprime(j)==false;
            }
        } return i;
    }
}
integralfx (897)
if(isprime(i)==true)
You don't need the ==true part.

isprime(j)==false;
This is a statement, and does nothing.

1
2
3
4
5
6
7
 
        if(isprime(i)==true)
        {
            for(int j=i*i; j<n; j+=i*i)
            {
                isprime(j)==false;
            }
        } return i;

You're returning on the first iteration.
Last edited on
nero1010 (7)
Thats what i was trying to use originally

1
2
3
4
5
6
7
8
 

for(int i=1; i<=sqrt(n); ++i)
{ if(isprime(i)=true)
    for(int j=1; j<=n; ++j)
      { if(isprime(j)=false) }
 }
return i;
Last edited on
SakurasouBusters (732)
What is the function pi() trying to return?
nero1010 (7)
the number of primes
integralfx (897)
I'm assuming pi is meant to return the number of primes from 1 to n.
1
2
3
4
5
6
7
8
 
unsigned int pi( unsigned long long n )
{
    unsigned int counter{};
    for( int i = 1; i < n; ++i ) {
        if( isprime( i ) ) counter++;
    }
    return counter;
}

Last edited on
SakurasouBusters (732)
1
2
3
4
5
6
7
8
9
10
11
12
13
 
unsigned long long pi(unsigned long long n)
{
    for(int i=1; i<sqrt(n); ++i)
    {
        if(isprime(i)==true)
        {
            for(int j=i*i; j<n; j+=i*i)
            {
                isprime(j)==false;
            }
        } return i;
    }
}


Should be : 
1
2
3
4
5
6
7
8
9
 
unsigned long long pi(unsigned long long n)
{
    int N = 0;
    for(int i = 2; i <= n; ++i)
    {
        if(isprime(i) == true) ++N;
    }
    return N;
}
Last edited on
nero1010 (7)
I tried both methods provided and not getting the correct output.
It should return 4 if I was to choose a number from 1 to 10 or 25 if I was to choose a number from 1 to 100.
SakurasouBusters (732)
What was the result you get when you tried my method?
Can you show us the function isprime()?
integralfx (897)

It should return 4 if I was to choose a number from 1 to 10 or 25 if I was to choose a number from 1 to 100.

1 isn't a prime number.
Derp.
Last edited on
nero1010 (7)
when I tried your method I got 16. 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
bool isprime(unsigned long long n)
{
    
    if(n==1)
    {
        return false;
    }
    for(int d=2; d<=n-1; ++d)
    {
        if(n%d==0)
        {
            return false;
        }
    }
    return true;
}
integralfx (897)
for(int d=2; d<=n-1; ++d)
By the way, you only need to loop up to and including the square root of n.
SakurasouBusters (732)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
bool isprime(unsigned long long n)
{
    
    if(n==1)
    {
        return false;
    }
    for(int d=2; d<=n-1; ++d)
    {
        if(n%d==0)
        {
            return false;
        }
    }
    return true;
}


Should be : 
1
2
3
4
5
6
7
8
9
10
11
 
bool isprime(unsigned long long n)
{
    int nFactors = 0;

    for(int d = 1; d <= n; ++d)
    {
        if(n % d == 0) nFactors++;
    }

    return (nFactors == 2);
}
cire (8284)
SakurasouBusters wrote:
What was the result you get when you tried my method?

Your "should be" function is equivalent to:

1
2
3
4
 
unsigned long long pi(unsigned long long n)
{
    return 0;
}


Another one of those low-quality responses...
nero1010 (7)
okay now my code is this but im still getting wrong output
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
bool isprime(unsigned long long n)
{
    int nFactors = 0;

    for(int d = 1; d <= n; ++d)
    {
        if(n % d == 0) nFactors++;
    }

    return (nFactors == 2);
}

unsigned long long pi(unsigned long long n)
{
    
    for(int i = 1; i <= n; ++i)
    {
        if(isprime(i) == true) ++n;
    }
    return n;
}
nero1010 (7)
still getting 16 btw
integralfx (897)
1
2
3
4
5
6
7
8
9
10
11
 
bool isprime(unsigned long long n)
{
    int nFactors = 0;

    for(int d = 1; d <= n; ++d)
    {
        if(n % d == 0) nFactors++;
    }

    return (nFactors == 2);
}

Your original code works, while this doesn't.
Brain derp(again).

1
2
3
4
5
6
7
8
9
 
unsigned long long pi(unsigned long long n)
{
    
    for(int i = 1; i <= n; ++i)
    {
        if(isprime(i) == true) ++n;
    }
    return n;
}

You're incrementing the number passed as an argument. You'll need some sort of counter to keep track of the number of primes. I really don't think you'll need to return an unsigned long long. An unsigned int is sufficient enough(up to about 4.3billion).
1
2
3
4
5
6
7
8
9
 
unsigned int pi(unsigned long long n)
{
    unsigned int counter{};
    for(int i = 1; i <= n; ++i)
    {
        if(isprime(i)) counter++;
    }
    return n;
}
Last edited on
SakurasouBusters (732)
Well, the working code is : 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
bool isprime(unsigned long long n)
{
    int nFactors = 0;

    for(int d = 1; d <= n; ++d)
    {
        if(n % d == 0) nFactors++;
    }

    return (nFactors == 2);
}

unsigned long long pi(unsigned long long n)
{
    int N = 0; // The counter variable should be this one
    for(int i = 1; i <= n; ++i)
    {
        if(isprime(i) == true) ++N;
    }
    return N;
}


@integralfx
Don't judge a book by its cover. At least test my code first before making any assumptions.
Last edited on
Topic archived. No new replies allowed.