C++

Forum

 
Finding the N-th(next) Prime number

princesslumy (36)
How to make the program run properly??

#include<cstdlib>
#include<iostream>
#include<cmath>
#include<cctype>
using namespace std;
int a,num;
int isprime(int a)
{
int n=0;
int num=0;
for (int i=1;i>=0;i++)
{
num++;
for (int j=2;j>=100;j++)
if (num%j==0 && num!=j)
return (0);
else if (num%j==0 && num==j)
n++;
}
if (n==a)
return(n);
}
int main ()
{
cout<<"Enter a positive integer: ";
cin>>a;
while (a<=0)
{
cout<<"Enter a positive integer: ";
cin>>a;
continue;
}
cout<<"the "<<a<<" th prime number is: "<<isprime(num)<<endl;
system("pause");
return 1;
}
nixer526 (17)
This isn't the best way to do it, but it should give you an understanding...
Personally I would also like to learn a better way of doing it, so if anyone else can improve the code, please feel free to do it.

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
 
#include<iostream>
using namespace std;
int isPrime (int num) {
    int nPrime = num+1;
    int pCounter = 0;
    bool primeFound = false;
    while (primeFound == false) {
        for (int i = 2; i < nPrime; i++) {
            if (nPrime % i == 0) {
                pCounter ++;
                break;
            }
        }
        if (pCounter == 0) {
            primeFound = true;
            pCounter = 0;
            return nPrime;
        } else {
        nPrime++;
        pCounter = 0;
        }
    }
    return 0;
}
int main ()
{
    int a;
    cout<<"Enter a positive integer: ";
    cin>>a;
    while (a<=0)
    {
        cout<<"Enter a positive integer: ";
        cin>>a;
        continue;
    }
    cout<<"the "<<a<<" th prime number is: "<< isPrime(a) <<"\n";
    return 0;
}
fg109 (709)
From the title, I thought the problem is finding the Nth prime. As in "Find the 10th prime" (29).

I am not exactly sure what the OP's code is supposed to do, and nixer526's code is just checking whether the number entered is a prime or not.

Many of the Project Euler problems deal with prime numbers, and this is the code I came up with for one of them:

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
 
/*	Project Euler #050

	The prime 41, can be written as the sum of six consecutive
	primes:
	41 = 2 + 3 + 5 + 7 + 11 + 13

	This is the longest sum of consecutive primes that adds to
	a prime below one-hundred.

	The longest sum of consecutive primes below one-thousand
	that adds to a prime, contains 21 terms, and is equal to 953.

	Which prime, below one-million, can be written as the sum
	of the most consecutive primes?

*/

/*	Thoughts

	The key terms here are "consecutive primes".  This makes it
	much easier, because it just means that we have to keep
	adding primes in sequence and then check if the sum is a
	prime, and if so, how close it is to a million.
	
	We will also need to check consecutive primes that don't
	start with a two though.
*/

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <ctime>

using namespace std;

int main()
{
	vector<long> Primes;

	const unsigned long long limit = 1000000;
	unsigned long i = 2;
	bool *IsPrime = new bool[limit];

	memset(IsPrime, true, sizeof(bool) * limit);
	IsPrime[0] = IsPrime[1] = false;

	while (i < limit)
	{
		Primes.push_back(i);
		for (unsigned long j = i; j * i < limit; j++)
		{
			IsPrime[i*j] = false;
		}
		if (i == 2)
		{
			i = 3;
		}
		else
		{
			do
			{
				i += 2;
			} while (!IsPrime[i] && i < limit);
		}
	}
	
	delete(IsPrime);
	
	unsigned long max_count = 0, max_prime = 0;
	for (i = 0; i < 100; i++)
	{
		unsigned long j, sum = 0, count = 0, prime = 0;
		for (j = i; sum + Primes[j] < 1000000; j++)
		{
			sum += Primes[j];
			if (find(Primes.begin(), Primes.end(), sum) != Primes.end())
			{
				count = j - i;
				prime = sum;
			}
		}
		if (count > max_count)
		{
			max_count = count;
			max_prime = prime;
		}
	}
	
	cout << max_prime << ", composed of " << max_count << " consecutive primes." << endl;
	
	cout << "Program run-time is " << clock() / CLOCKS_PER_SEC << " seconds." << endl;
	return 0;
}


Lines 39 to 68 is my implementation of the Sieve of Eratosthenes. It is basically me storing the primes up to 1000000 inside a vector called Primes.
Last edited on
nixer526 (17)
I thought the OP ment to look for the next prime number that he entered...
So for example, if he entered 13 and was looking for the next prime number, it would be 17...

I might be wrong though.

Thanks for the share fg109. Your's seems to be what the OP might be requesting.
Topic archived. No new replies allowed.