Prime Number using while loop only

[Zain129]

I have to write a program to find "1" to "n" prime numbers using while loop.
"n" is the number entered by the user.
e.g. If n=8, it should print first 8 prime numbers which are 1,2,3,5,7,11,13,17 and vice versa.

[andywestken]

Well, what's your first attempt?

Or if you haven't got any code yet, what is the first part of the problem to solve?

Andy

[jumper007]

We, here, do not solve your homework. We are just helping you understand the way it should be done or correct your mistakes after your first approach if not successful. You'd better try to write your code, and if you occur any issues, let us know.

Good luck.

[ResidentBiscuit]

Finding prime numbers is a common problem given while studying, because it's an interesting problem with no clear solution while having many good solutions at the same time. So I'm going to encourage you to try to do this on your own first. Like I say with any program when someone has trouble, just think of each problem as a set of problems, and then work on solving each element of that set. Basically, break this into more manageable tasks.

[Zain129]

Actually i know how to find prime numbers!!!
IF (number%2 !=0 && number%3 !=0 && number%5 !=0)
THEN it is prime number but i dont know how to use while loop.

while(i<=n) //n is the number entered by user and defined above
{
cout<<(number+1);
n--;
}

Is it true?????

[ResidentBiscuit]

IF (number%2 !=0 && number%3 !=0 && number%5 !=0)

That's not true at all.

[TheIdeasMan]

If I could explain to the OP why it isn't true.

Consider 2 prime numbers multiplied together, the answer is not prime, because the 2 primes are factors!!!

So you have to come up with an efficient way of checking that each previous prime is not a factor.

[jumper007]

There is actually a specific algorithm for checking whether a number is prime or not!
There is also an algorithm for generating the first 'n' prime numbers!

If you need explanations or want me to help you understand those algorithms just write me a Private Message or on my email: [e-mail]

[Nobun]

yeah, true jumper007. Even if I never studied math (except for basic school) I knew it so I would add that there is no-way to calculate prime numbers or checking if prime. I also know some solutions were found limiting the search field (more or less until the 200th prime number I remembered to hear).

It is a very interesting math "problem"...

[jumper007]

Sorry for double post.
Here is one example, of the many ways to check a number:

#include <iostream>

using namespace std;

bool isPrime (int number);

int main()
{
    int x;

    cout << "Give a number: "; cin >> x;

    // Will print '1' in case the number is prime and '0' otherwise
    cout << isPrime(x);

    return 0;
}

// Predicate, which returns whether an integer is a prime number
bool isPrime (int number)
{
    // 0 and 1 are prime numbers
    if (number == 0 || number == 1) {
        return true;
    }

    // Find divisor that divides without a remainder
    int divisor;

    for (divisor = number/2; number%divisor != 0; --divisor) {
        ;
    }

    // If no divisor greater than 1 is found, it is a prime number
    return divisor == 1;
}

EDIT: Sure, there is a limit in the generating algorithm, also called the "Sieve of Eratosthenes". That limit, as Nobun said, is about 200. That's the point where it usually stops. But anyways, there have been programmers (at least in my country), which have developed an optimised version which uses bitsets and/or bitwise (maybe harder to understand for many of us), and from what I heard, it goes even further with generating.

[brandonator]

thought of an easier way, 1+3+5+7+9 ect. make prime numbers (two difference)

so

int main()
{
int numbers;
int x = 0;
int n = 1;
cout << "how many numbers do you want?" << endl;
cin >> numbers; 
while x > 0 && z < numbers;
{
    x = x + n;
    n = n + 2;
    cout << x << endl;
    z = z + 1;
}
cin.get();
return 0;
}

just created this from scratch so there may be a few bugs but the easiest way i could think of of making prime numbers from 1 to your amount of numbers, and cin.get() was to pause until user hits enter && was the 'and' command

[TheIdeasMan]

@brandonator (67)

thought of an easier way, 1+3+5+7+9 ect. make prime numbers (two difference)

That's not right either. 9 is not prime. The sum is 25 which isn't prime. Most of the partial sums are not prime. Not all odd numbers are prime.

What did you mean?

Maybe you should alter the code until you can get it to compile, then verify the results.

[jumper007]

@brandonator Actually, no. The Sieve of Eratosthenes is a given algorithm and works like a charm. Here is one of the edited versions to count the number of prime numbers from 1 to n (actually this one is the fastest I know -- 12ms in execution for n = 2.000.000)

#include <cstdio>
#include <bitset>
#include <cmath>

using namespace std;

int main()
{
	bitset<1000010> viz;
	viz.reset();
	
	int n;
	freopen("ciur.in", "r", stdin);
	freopen("ciur.out", "w", stdout);
	
	scanf("%d", &n);
	
	if(n == 2)
	{
		printf("%d\n", 0);
		return 0;
	}
	
	int i;
	
	if(viz[500000])
		;
		
	for(i = 1; i <= (sqrt((double)n) / 2); i++)
	{
		if(!viz[i])
		{
			int x = ((i << 1) + 1) * ((i << 1) + 1);
			
			while(x < n && x > 0)
			{
				if(x % 2) viz[x >> 1] = 1;
				x += (i << 1) + 1;
			}
		}
		
	}
	
	printf("%d\n", n - viz.count() - (n-1)/2 - 1);
	
	return 0;
}

[brandonator]

@TheIdeasMan

yeah i accedently made the 'perfect squares' one :P , my bad