I'm trying to write a program that prints out all prime numbers from 1 to 300. It isn't working the way I want it to. Right now it appears to have caused an infinite loop. Here is my code.

#include<iostream>
#include<iomanip>

using namespace std;

int main(){
	for(int i=0; i<=300; i++){
		for(int j=2; j<300; j++){
			if(i%j!=0){
				cout<<j <<endl;
			}
		}
	}
}

The logic of your code is wrong. It is not an infinite loop but you are going to print out a lot more than you meant to.

What happens at the moment when, for example, i = 40 and j = 30?

Edited 5 Years Ago by Moschops: n/a

The logic of your program is wrong.A prime number has only two factors,1 and the number itself.In your program odd numbers would be displayed because it is not divisible by 2.
15%2!=0 ,so 15 will be displayed though its not a prime number.
Try this one

int c,d,e=0;
for(c=2;c<=300;c++)     //excluding 1 as 1 is neither prime nor composite
{for(d=2;d<300;d++)
 {if(c%d==0)
  {e=e+1;   //keeping count of the factors
  }
 }
 if(e==1)
 {cout<<c<<" ";
 }
 e=0;
}

There are many tests you can perform on numbers to see if prime & one such test is known as the "Miller Rabin Test".
I recommend reading about this test here http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test

Its not an easy test to code without a good understanding of the algorithm, so here is a working example of this test with two example usage's

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

using namespace std;
/**
    Miller Rabin Test to see if prime number, Handy test
    for larger intergers "this test is about 99.9% accurate"

    Recommended reading on this test can be found here
    http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test

*/
bool Miller_Rabin_Test(int64_t n, int64_t alpha)
{
    int64_t q = n-1;
    for (int64_t i=1; i<=(alpha*log(n)); i++)
    {
        int64_t m = q, y = 1;
        int64_t a = rand() % q + 1;
        int64_t z = a;
        while (m > 0) {
            while (m%2 == 0) {
                int64_t x = z; z = (z*z) % n;
                if ((z==1) && (x != 1) && (x != q))
                return(false);
                m /= 2;
            }
            m--; y = (y*z) % n;
        }
        if (y != 1) return(false);
    }
    return(true);
}



int main()
{
    /**
    Get all prime number between two values
    Example 1.
    */
    int64_t start_of_range = 1;
    int64_t end_of_range = 300;
    cout << "Example[1] All prime numbers between range::"<<start_of_range<<" & "<<end_of_range<<endl;

    int c=0;
    for(int i=start_of_range; i < end_of_range; i++){
        bool prime = Miller_Rabin_Test(i, 3);
        if (prime == true){

            if (c == 9){
                cout << "\r\n";
                c = 0;
            }
            cout << i << " " ;
            c++;
        }
    }
    cout << "\n\n";

    /**
    Test to see if single number is prime
    Example 2.
    */
    int64_t number_to_test = 354657654;
    cout << "Example[2] Test a single number if prime::"<<number_to_test<<endl;
    bool prime = Miller_Rabin_Test(number_to_test, 3);
        if (prime == true){
            cout << "Is a prime number::" << number_to_test << endl;
        }else{
            cout << "Is not a prime number::" << number_to_test << endl;
        }

}

This test is about 99.9% accurate in most cases, it does not create prime numbers but rather the Miller–Rabin test relies on an equality or set of equalities that hold true for prime values.

Hope this helps

look here's the problem...if u want to check whether the number is prime or nt.....u shud follow this logic...

#include<iostream>
using namespace std;
bool pri(int);
int main()
{
    for(int i=1;i<=300;i++)
    {
            if(pri(i))
            {cout<<i<<" ";}
    }
    system("pause");
    return 0;
}
bool pri(int n)
{
     for(long int i=2;i<=n/2;i++)
     {
             if(n%i==0)
             return false;
     }
     return true;
}

in order to find out whether a numbr is prime r nt we only need to divide it till half of its value...and if it doesnt get divided by any of the numbers in the first half then it wont be divided by any number in the 2nd half fr sure....

Edited 5 Years Ago by Nick Evan: Added CODE-tags. After 19 posts, you could've figured out how they work.

in order to find out whether a numbr is prime r nt we only need to divide it till half of its value...and if it doesnt get divided by any of the numbers in the first half then it wont be divided by any number in the 2nd half fr sure....

No square root will suffice.

P.S please use code tags.

Edited 5 Years Ago by frogboy77: n/a

Ok think of it like this;

if you tried to divide by 2 and it didn't work then anything over n/2 can't be a factor.

if you tried to divide by 3 and it didn't work then anything over n/3 can't be a factor.

if you tried to divide by 5(no point in 4 as 2 didn't work) and it didn't work then anything over n/5 can't be a factor.

etc.. etc..

until you come to the square root.

@The Bowie fan

I tried recently to write a miller-rabin function and failed:(

How reliable do you think this code is (i.e have you tested it?) given the simple omission already noted?

Frogboy77
If you are refering to the Miller Rabin Test algorithm 99.9% in most case's I believe, if you mean the coding no it's not been properly tested by me, but the results so far have looked OK. Speed seems to be a big plus with this algorithm as you will see if to try it with a large number sets.

I give the alogrithm the thumbs up.

Sorry about that frogboy77...

Here is another bit of code that does the Miller-Rabin primality test, maybe you can have a play with and do some tests & compare results.

#include<iostream>
#include <math.h>
#include <cstdlib>
#include <ctime>
using namespace std;
/* this function calculates (a*b)%c taking into account that a*b might overflow */
long long mulmod(long long a,long long b,long long c){
    long long x = 0,y=a%c;
    while(b > 0){
        if(b%2 == 1){
            x = (x+y)%c;
        }
        y = (y*2)%c;
        b /= 2;
    }
    return x%c;
}
/* This function calculates (ab)%c */
int modulo(int a,int b,int c){
    long long x=1,y=a; // long long is taken to avoid overflow of intermediate results
    while(b > 0){
        if(b%2 == 1){
            x=(x*y)%c;
        }
        y = (y*y)%c; // squaring the base
        b /= 2;
    }
    return x%c;
}
/* Miller-Rabin primality test, iteration signifies the accuracy of the test */
bool Miller(long long p,int iteration){
    if(p<2){
        return false;
    }
    if(p!=2 && p%2==0){
        return false;
    }
    long long s=p-1;
    while(s%2==0){
        s/=2;
    }
    for(int i=0;i<iteration;i++){
        long long a=rand()%(p-1)+1,temp=s;
        long long mod=modulo(a,temp,p);
        while(temp!=p-1 && mod!=1 && mod!=p-1){
            mod=mulmod(mod,mod,p);
            temp *= 2;
        }
        if(mod!=p-1 && temp%2==0){
            return false;
        }
    }
    return true;
}

int main()
{
    /**
    Seed random generator
    */
    srand ( time(NULL) );
    for(int i=100000000;i<=100005000;i++)
    {
        bool result = Miller(i,3);
        if (result == true){

          cout << " " << i << endl;

        }
    }

    return 0;
}

@ziggystarman

Having just reread your comments on my code snippet i have a question:

is this your own work?

I've posted on various forums for related topics, I am doing research in computer vision + machine learning so it's quite possible you've seen my name crop up.

This article has been dead for over six months. Start a new discussion instead.