Member Avatar for ViperVenomHD

Hi guys. I am trying to create a program where the user inputs an integer and the program will cout the nth prime number. Unfortunatly when I try to cout just the nth prime number it doesn't work. However theoretically if I have the program print out all of the prime numbers up to the nth prime number, it just prints out 3,4,5,6,7,8 etc. UI means userinput in my code. 

#include<iostream>
using namespace std;

int main(){
    unsigned int UI; // userinput
    int counter1 = 1; // number of primenumbers
    bool isprime = true;
    int primenumber = 3; //number that it is checking to see if it is prime. 
    cout << "Enter in a positive integer" << endl;
    cin >> UI;
    while(UI == 0){
        cout << "Invalid input. Please try again" << endl;
        cin >> UI;
    }
    if(UI == 1){
        cout << endl << "2"<< endl;
    }
    else if(UI == 2){
        cout << endl << "3" << endl;
    }
    else if(UI > 2){
        while(counter1 != UI){
            isprime = true;
            cout << primenumber << ",";
            for(int checker = 2; checker < primenumber; checker++){
                if(primenumber % checker == 0){
                    isprime = false;
                    break;
                }
            }
            if(isprime == true){
                counter1++;
            }
            primenumber++;
        }
        if(counter1 == UI){
            cout << primenumber << endl;
        }
    }

}
  • 4 Contributors
  • 4 Replies
  • 896 Views
  • 1 Week Discussion Span
  • Latest Post Latest Post by tinstaafl

Dani AI

Generated

A short, practical path forward (and what went wrong)

’s loop was printing each candidate before checking it for primality, so you saw the integers rather than only verified primes; caught the counting/first-prime issues. For a user-entered n, avoid trial-division loops for large n — instead generate primes up to a safe upper bound and pick the nth one. The standard, easy-to-implement choice is the Sieve of Eratosthenes. (en.wikipedia.org)

How to pick the sieve size

Use a provable upper bound for the nth prime so the sieve contains the answer. For n >= 6 a common bound is
p_n < n*(ln n + ln ln n),
so compute that (with a small safety margin) to size the sieve array. That keeps the algorithm deterministic and efficient for a wide range of n. (en.wikipedia.org)

Compact C++ sketch (simple sieve + bound)

#include <iostream>
#include <vector>
#include <cmath>

size_t upper_bound_nth_prime(size_t n) {
    if (n < 6) return 15;
    double nn = double(n);
    return size_t(nn * (log(nn) + log(log(nn))) + 10.0);
}

int main() {
    size_t n;
    if (!(std::cin >> n) || n == 0) return 0;
    size_t limit = upper_bound_nth_prime(n);
    std::vector<char> is_prime(limit + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (size_t p = 2; p * p <= limit; ++p)
        if (is_prime[p])
            for (size_t m = p * p; m <= limit; m += p)
                is_prime[m] = false;
    size_t count = 0;
    for (size_t i = 2; i <= limit; ++i)
        if (is_prime[i] && ++count == n) { std::cout << i << '\n'; break; }
}

Notes and next steps

The simple sieve is O(limit log log limit) time and works well for n up to millions; for very large n use a segmented sieve to keep memory small and cache-friendly. If experimenting with primality tests, note that general-purpose proofs like AKS (as mentioned by ) are not practical here — sieves or probabilistic/fast deterministic tests are the right tools for generating many primes. (geeksforgeeks.org)

Recommended Answers

All 4 Replies

Member Avatar for tinstaafl

Actually your algorithm is mostly correct. what you were forgetting is that 2 is the first prime number, but you weren't printing that.

Even though your algorithm is naive, there are some optimizations worth mentioning:

The greatest number that needs to be checked if it's a factor is the square root of the number. Everything that's a factor after that, its reciprocal has already been checked.

After 2 all the other primes are odd. Therefore, you only need to check the odd numbers.

Here's your code, that keeps all this in mind. Plus a few other tweaks:

#include <cmath>
#include<iostream>
using namespace std;

int main()
{
    unsigned int UI; // userinput
    cout << "Enter in a positive integer" << endl;
    cin >> UI;
    while (UI == 0)
    {
        cout << "Invalid input. Please try again" << endl;
        cin >> UI;
    }
    if (UI == 1)
    {
        cout << endl << "2" << endl;
    }
    else if (UI == 2)
    {
        cout << endl << "3" << endl;
    }
    else if (UI > 2)
    {
        int counter1 = 1; // number of primenumbers
        bool isprime = true;
        int primenumber = 3; //number that it is checking to see if it is prime.         
        cout << 2;
        while (counter1 != UI)
        {
                isprime = true;
                int limit = sqrt(primenumber);
                for (int checker = 3; checker < limit; checker += 2)
                {
                    if (primenumber % checker == 0)
                    {
                        isprime = false;
                        break;
                    }
                }

            if (isprime == true)
            {
                cout << "," << primenumber;
                counter1++;
            }
            primenumber += 2;
        }
        cout << '\n';
    }
}

On a side note. Try to always keep the declaration of your variables as close as possible to where you first need them. On a small project, this is kind of a moot point. But, on a large project it is invaluable.

Edited by tinstaafl
Member Avatar for rproffitt

Just a tip. Many wheels can be had from stock. That is, functions like the test for prime has many ready to use solutions. Bolt that on and run.

Look at the is_prime() function in C at https://rosettacode.org/wiki/AKS_test_for_primes

Rosettcode is a treasure trove of ready to use functions.

Member Avatar for Adeniyi_3

great

Member Avatar for tinstaafl

FYI, there is as small bug in my post the for loop should read:

for (int checker = 3; checker <= limit; checker += 2)
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.