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?
main() is prototyped to return an int, but returns nothing.
main() is prototyped to return an int, but returns nothing.
Actually, that's ok according to the standard. A return of 0 is implied if none is specified.
i think (i=2,i<300,i+=2)
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
Where is rand seeded?
it's not, well spotted
int main()
{
/* initialize random seed: */
srand ( time(NULL) );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....
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.
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.
I was referring to your code and not the algorithm itself.
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;
}thanks, i will have a play about with it:)
No problem
@ziggystarman
Having just reread your comments on my code snippet i have a question:
is this your own work?
No it's some stuff I've been playing about with the past few weeks to get a understanding myself of the algorithm's used to test prime's.
See here for tutorial...
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=primalityTesting
Hope this helps
Your name seems familiar, are you a Euler regular?
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.
You can see this post if you wish.
http://www.mahfuzsust.info/2013/10/10/prime-numbers-sieve-of-eratosthenes/
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.