Find prime numbers between random numbers

[Ausha]

Hi! People here are talking a lot about prime numbers, but i just couldn't find the right answer. I need to write program, that generates numbers from 1 to a (any input number) and then determine, which between these are prime and which are not, And this just doesn't work from the part where prime is calculated.

#include<iostream>
#include<math.h>
using namespace std;
int main ()
{
int a;
cin>>a;
for(int b=1; b<=a; b++);
{
bool prime;
for (int c=2; c<=b; c++);
if(b%c==0)
prime=false;
{ cout<<b <<"is not prime"<<endl;}
else if (b%c!==0)
prime=true;
{ cout<<b <<"is prime"<<endl;}
}
}
system ("pause");
return 0;
}

[MiiNiPaa]

1) learn to modularise your program: routine to check number for prime attribute could be moved to it's own function bool isPrime(int n)
2) Your prime detection algorithm is wrong : first, prime variable is uninitialisated; second, c<=b is a disaster: when c==b c%b is always 0.
3) Identation would help.
4) you need to completely rewrite everything between and including two output statements. Remember: output should be decoupled from prime detection.

[Ausha]

I know this is a disaster, that's why I am asking for help :)

[Chervil]

There are a few things wrong,

    for(int b=1; b<=a; b++);

and

    for (int c=2; c<=b; c++);

Each of these lines ends with a semicolon, which should not be there.
Also, there are mismatched opening and closing braces { }.

In the second loop, I would treat b==1 and b==2 as special cases (1 is not prime, 2 is prime). For the other numbers, the loop condition should be c<b instead of c<=b

[Ausha]

Thanks a lot, your advice helped a lot! Just my prime number definition still is wrong. I will try to fix that and then post the ready right code.

[Ausha]

Solved it! This is how it works!

#include<iostream>
#include<math.h>
#include<ctime>
using namespace std;
int main ()
{
srand (time(0));
int a;
cout<<"Input the number!"<<endl;
cin>>a;
for(int b=1; b<=a; b++)
{
    bool prime;
    if ((b==2)||(b==3)){prime=true; cout<<b<<" is prime"<<endl;}
    else if ((b%2==0)||(b%3==0)) {prime=false;cout<<b<<" is not prime"<<endl;}
    else {prime=true; cout<<b<< is prime"<<endl;}
}
system("pause");
return 0;
}

[Chervil]

Sorry, that code incorrectly reports that 1, 25, 35, 49, 55 (and an infinite number of others) are prime.

[Ausha]

Ok little changes! this definetely is working!

#include<iostream>
#include<math.h>
#include<ctime>
using namespace std;
int main ()
{
srand (time(0));
int a;
cout<<"Ievadi veselu skaitli"<<endl;
cin>>a;
for(int b=1; b<=a; b++)
{
    bool prime;
    if ((b==2)||(b==3)){prime=true; cout<<b<<" ir pirmskaitlis"<<endl;}
    else if ((b%2==0)||(b%3==0)||(b%5==0)||(b%7==0)||(b%9==0)) {prime=false;cout<<b<<" nav pirmskaitlis"<<endl;}
    else {prime=true; cout<<b<<" ir pirmskaitlis"<<endl;}
}
system("pause");
return 0;
}

[Ausha]

Oh dont even need (b%9==0) becouse its the same as with 3 but needed 5 and 7

[keskiverto]

That does not go far. Is 121 a prime? How about 5?

You should keep a list of the primes you have already found, add each new prime to it, and use that list to determine whether the next value is a prime.

[Chervil]

But the method is by it's nature an incomplete solution. It will always fail if you check a few more numbers. In order to succeed with this approach, your program would need to be infinitely long. There are better, more general ways of tackling the problem.

Latest version gives incorrect result for:
1, 5, 7, 121, 143, 169,187...

[Ausha]

I tried to create a control number like (int i=2; i<30; i ++) and then check if (b%i==0), but then it checks the number 30 times and each times writes a comment which is wrong each time :(

[Ausha]

yes but as it is now, then i should write also to check the numbers with 11, 13, 15,17,19, and thats too long

[keskiverto]

MiiNiPaa wrote:

1) learn to modularise your program: routine to check number for prime attribute could be moved to it's own function
4) ... Remember: output should be decoupled from prime detection.

[machinafour]

Here is one of the functions I wrote to check if a number is a prime:

bool is_prime(int x) {
	
	int z = 0;
	for(int a = 1; a < x; a++) {
		if(x % a == 0) z++;
	}
	if(z==1) return true;
	else return false;
}

Note: there are faster variations of this function, for example you actually only need to loop up to sqrt(x).

Then, in your program you can call is_prime with your b variable:

if(is_prime(b)) cout << b << " is prime << endl;
else cout << b << " is not prime << endl;

[MiiNiPaa]

More effective algorithm:

#include <iostream>
#include <vector>
#include <algorithm>

bool isPrime(unsigned n)
{
    static std::vector<unsigned> primes({2, 3, 5, 7});
    static unsigned last_checked = 7;

    for(unsigned i = last_checked + 1; i <= n; ++i) {
        bool is_prime(true);
        for(auto j: primes)
            if ((i % j) == 0) {
                is_prime = false;
                break;
            }
        if (is_prime) {
            primes.push_back(i);
        }
    }
    return std::binary_search(primes.cbegin(), primes.cend(), n);
}

int main()
{
    std::cout << isPrime(37);
}

[GRex2595]

As long as we're all giving answers.

#include <iostream>
#include <math.h>

using namespace std;

bool isPrime(int);

int main()
{
    int max;

    cout << "Enter max number:  ";
    cin >> max;

    for(int x = 2; x <= max; x++)  //1 is technically not a prime number.  Don't ask me
    {
        if(isPrime(x))
            cout << x << " is prime\n";
        else
            cout << x << " is not prime\n";
    }

    return 0;
}

bool isPrime(int num)
{
    if(num <= 1)
        return false;

    int root = sqrt((double)num);

    //start at 2 because all numbers are divisible by 1
    for(int x = 2; x <= root; x++)  //You only need to check up to and including the root
    {
        if(num % x == 0)
            return false;
    }

    return true;
}

@MiiNiPaa
Did you compile your code? I got about 14 compiler errors.

[Chervil]

@GRex2595 Your code looks sensible.
However, in this case rather than starting the loop at line 15 with x=2, you could start from 1, and insert after line 27

    if (num == 1)
        return false;

[MiiNiPaa]

Wait, if he will start loop from one, on line 33 he would be testing (num % 1 == 0) which is always true

@GreX2595 Turn on C++11 mode

[GRex2595]

Good point. Although, since it's an unsigned int, that code would not even be enough. If I did it correctly it would actually be something more like

if(num <= 1)
    return false;

I updated the code in the last comment so it can be used directly.