CODEWITHSUNDEEP
c++algorithmprimes
user6889367
user6889367

Reputation: 123

Code to print Nth prime number

I have to print the Nth prime number. For example:
1st prime number is 2
2nd prime number is 3
.
.
10th prime number is 29 and so on....

My algorithm is as follows:
1) Add 2 and 3 to stack.
2) If n <= Size of stack, get item at position n and output answer
3) Else, start from last element of stack, check if prime
4) To check for prime, divide from each element in stack. If remainder 0 for any element in stack, not a prime. Break loop
5) If Prime, add to stack
6) Search only odd numbers

My code is :

#include <iostream>
using namespace std;

int main() {
    int number, count = 0;
    cin >> number;          //position of prime number
    int a[number];
    a[0] = 2;
    a[1] = 3;
    int top = 1;
    if (number <= 2) {
        cout << a[number - 1] << endl;
    } else {
        for (int i = 5; i <= 10001; i += 2) {
            for (int j = 0; j <= top; j++) {

                if (i % a[j] != 0) {
                    count++;

                }
                if (count == (top + 1)) {
                    a[++top] = i;
                    if ((count + 1) == number) {
                        cout << a[top];
                        break;
                    }

                }

            }

        }

    }
    return 0;
}

This code abruptly stops working without giving any output.What is the flaw in my code?

Upvotes: 1

Views: 6646

Answers (3)

Ali Hoşg&#246;n&#252;l
Ali Hoşg&#246;n&#252;l

Reputation: 1

    Scanner s = new Scanner(System.in);
    int n = s.nextInt();
    int j=2;
    boolean bool=true;
    int counter=0;
    int i=1;
    while(counter<n)
    {
        i++;
        bool=true;
        for(j=2;j<i;j++)
        {
           
            if(i%j==0)
            {
                bool=false;
            }
  
        }
        if(bool)
        {
            counter++;
            System.out.println(counter+". prime number is: "+i);
        }
      
    }

Upvotes: 0

samgak
samgak

Reputation: 24417

It's a problem with your looping logic. You need to trial divide i by all the numbers from 0 to top on your stack, and only if i is divisible by none of them do you increase count. As it is you are increasing it if it is indivisible by any of them.

So, change the logic to test ifi is divisible by a[j]. If it is, then break out of the loop. If you reach the end of the loop (j == top) and it hasn't successfully divided any of them then you know it's prime and you can increase count. Also, the check where you compare count to top should be outside of the j loop (i.e. after you have done all the trial divisions)

    for (int i = 5; i <= 10001; i += 2) {
        for (int j = 0; j <= top; j++) {
            if (i % a[j] == 0) {
                break;
            }
            if(j == top)
            {
                count++;
                a[++top] = i;
                break;
            }
        }
        if (count == number) {
            cout << a[top];
            break;
        }
    }

Edit: you also need to initialize count to 2, not 0, to account for 2 and 3.

Upvotes: 1

macroland
macroland

Reputation: 1025

int a[number]; is wrong as number is not a constant. Rather you would like to write it as int *a=new int[number]

Upvotes: 0

Related Questions