Prime Numbers Help?

[s21122012]

I'm currently trying to detect and print prime numbers. Here's what I've got for now, but I get an error from the compiler: non-lvalue in assignment, and I can't seem to be able to fix that. Any help?

#include<iostream>
using namespace std;

int main() {
    int i, j;
    for(i=0; i<100; i++) {
        for(j=0; j<i; j++) {
            if(i%j=1 && i%j=i) {
                cout<<"Prime"<<endl;
            }
            else {
                cout<<"Not Prime"<<endl;
            }
        }
    }
}

[Mybowlcut]

if(i%j=1 && i%j=i) {

should be

if(i%j==1 && i%j==i) {

= for assignment, == for equality.

[AmadeusAD]

You have also ill-formed logic for your task. Consider, that % operator returns the remainder, not the bool value 'divisable'. For determining whether i is divided by j, you have to determine whether the i%j value is zero, and vice versa.

[jefranki]

Also note:

anything%0; //divide by zero error

[simonovic]

agree with amadeus, use % to detect non-primes if its equal to 0 for any j, if not 0 for any j>1 then say its prime

another way is

int nonprime[100];//initialize all elements to 0 

for(i=0; i<100; i++) {
        for(j=2; j<=i; j++) {
nonprime[i*j]=1;
}

thus at the end nonprime array is a bitvector, if a index is 1 its nonprime (i.e. nonprime[50]=1 while nonprime[47]=0 at the end of execution )

[s21122012]

I re-wrote the program, and it only works for interval 1-3. The problem is within the second loop, I guess.

#include<iostream>
using namespace std;

int main() {
    int l;
    cout<<"Please enter an interval limit (0-N): ";
    cin>>l;
    for(int i=0; i<=l; i++)
    for(int n=1; n<l; n++)
    if(i%n==1)
    cout<<i<<" ";
    return 0;
}

[AmadeusAD]

Again, i % n == 1 is a check whether i is divided by n with remainder 1. That is not probably what you want. If you want to check whether i has a divider different from i and 1, then you should (in your way) iterate all the numbers from 2 to (i - 1), and if somewhere i % n == 0 (say n is the iterator), then i is not prime. Otherwise, if the loop reaches its end, the i is prime.
Note, that there are lots of algorithms for detecting primes, and iterating from 2 to (n - 1) is not neccessary, since it takes much time on presumably unneccessary checks (you could increase step to 2, iterate up to sqrt(n - 1), etc) - but the one you are trying is the simplest one for understanding your task.
Hope that helps.

[s21122012]

That's also something I've tried. The original program had n=2; n<(i-1). Here's the latest version. It should work (if you enter 3, then it checks if 1:2, 2:2 or 3:2 has remainder 0, and if it doesn't, display the number. it displays me no numbers...).

#include<iostream>
using namespace std;

int main() {
    int l;
    cout<<"Please enter an interval limit (0-N): ";
    cin>>l;
    for(int i=1; i<=l; i++)
    for(int n=2; n<=(i-1); n++)
    if(i&#37;n!=0 && i%n==i && i%n==1)
    cout<<i<<endl;
    return 0;
}

[AmadeusAD]

Not surprisingly that no numbers are displayed. Look at your condition - it is always false since i&#37;n cannot be both i and 1 at the same time. Why do you still code that annoying i%n==1 check? What are going to see? Again - i%n - is the REMAINDER, and i%n==1 means that i = n*k + 1... And: i%n==i - is totally impossible when i >= n, since the remainder is 0..(n-1) number. So, throw those two annoying bad checks away - and invert logic of the first one to i%n==0 - then your program will display non-prime numbers.

[s21122012]

Ok, now it does print non-prime numbers, but it displays each of them too many times. The output for 10 is something like 4 6 6 8 8 9 10 10. I can figure out I have to make it pass to the next value as soon as i checks (for example, if 6&#37;2 is true, don't check 6%3, but get to 7%2).

I know I'm doing it the wrong way, but I'm trying to actually display PRIME numbers. Using the non-primes algorithms, I'd like to create a vector of l elements, including integers from 1 to l. After using the algorithm, erase the generated numbers from the vector, and then print the rest of the numbers. I'm excluding the non-prime elements from the interval. But can I erase without specifying a position?

[toraj58]

i write the code for you:

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

using namespace std;

int main() {
    int i, j;
    for(i=2; i<100; i++) 
    {
        bool isPrime = true;
        for(j=2; j<=sqrt(i); j++) 
        {
            if(i&#37;j ==0 ) 
            {
                isPrime = false;
                break;
                
            }
           
        }
        
        if (isPrime)
        {
           cout<< i << " : Is Prime" << endl;          
        }else
        {
           cout<< i << " : Is not Prime" << endl;      
        }
    }
    system("PAUSE");
    return EXIT_SUCCESS;
}

according to a math theory it is just enough to test for 0 remainder till reaching sqrt(i). so i used that theory to have faster algorithm

[s21122012]

I appreciate this very much, but I'm not necessarily trying to print prime numbers. I'm reading a book, and the exercise wants me to detect and print prime numbers using 2 for loops and the modulus operator.

Here's my latest code. I put that break over there because w/o it, the program would have checked for numbers which would not eventually give the remainder 0. Now it works fine, but it does print the ones which are divided by odd numbers (for example, on 1-16, it prints 9 and 15, but excludes any number which is dividable by 2). I know n doesn't go further than 2 because of that break, and it drives me crazy.

#include<iostream>
using namespace std;

int main() {
    int l;
    cout<<"Please enter an interval limit: ";
    cin>>l;
    for(int i=1; i<=l; i++) {
    for(int n=2; n<l; n++) {
    if(i&#37;n!=0) {
        cout<<i<<endl;
    }
    break;
    }
}
    return 0;
}

[laserlight]

according to a math theory it is just enough to test for 0 remainder till reaching sqrt(i). so i used that theory to have faster algorithm

Though if you actually want to benefit from the theory, you should compute the square root just once, store the result, and then use that in the loop.

EDIT:
s21122012, you might want to consider naming your variable with a better name than l. For one thing, a one letter variable name is not descriptive in that context, and for another thing, l looks like 1 on some fonts, including the one this message board uses by default. You also need to indent your code better.

[toraj58]

yes that was also a performance hit.
it should be out of the second loop.

[AmadeusAD]

Furthermore, you can replace ++i in both loops with i+=2 with some slight check adding outside the loop.