Prime Number Generator... Help !?!!

So we have an assigment in class to make a program that produces 100 random numbers prints the randoms to a txt then outputs the prime numbers. I am almost sure this code is working ut I am at my GF house and she has some getto C++ compiler can someone run this for me and see if I error. And if I do what is wrong ????

Thanks in advance !

Code:

---

#include<iostream.h>
#include<iomanip.h>
#include<stdlib.h>
#include<time.h>
#include<fstream.h>
#include<math.h>


int main()
{
int numx;
int i, max, p;
char stop;
ofstream outputfile ("randnums.txt");

srand(time(0)); //this will produce a new number after each execution.

int array[100];

for(int z = 0;z < 100; z++) // Produces 100 random numbers
{
numx = 1+rand()%250; // Numbers range from 1-250
array[z]=numx;
outputfile << numx << endl; //inputs numbers into array
}

outputfile.close();


for(i = 0; i < 100; i++)
  {
  max = sqrt(array[i]);
  bool prime = true;
  for(p = 2; (p <= max) && prime; p++)
        {
        if((p % array[i]) == 0)
        prime = false;
        }
  cout << array[i] << " ";
        }

cin >> stop;

return 0;
}

---

When I run it, it just prints a huge string of seemingly random numbers, not just prime numbers, to the screen.

What are you trying to do? Your post isn't very clear on your goal. Why do you base your calculations on the square root of the current array element, then on the modulus between the array element and an incrementing value?

The following code would just delay the printing of the array element:

Code:

---

for(p = 2; (p <= max) && prime; p++)
{
        if((p % array[i]) == 0)
                prime = false;
}
cout << array[i] << " ";

---

No matter what happens, the array element is printed. I think you need to work through your program on paper first, figure out what is supposed to happen, then start coding.

Okay what I need to do is have a program the prints 100 random numbers to the txt file. Then after that the program sorts through the 100 random numbers and outputs those on the screen.

The Sqrt and the % tell if it is a prime number. If p is equal to zero after the Sqrt and the % then it is a prime number.

Well, p % array[i] will always return p, because p < array[i].

Perhaps you mean array[i] % p?

Code:

---

bool isprime(int n)
{
  double max=sqrt(n);
  for(int i=2; i<=max; i++)
  {
    if(n % i == 0)
      return false;
  }
  return true;
}

---

You might find that function useful. I use it in practically any program that deals with primes.

Slightly more efficient:

Code:

---

bool isprime(int n)
{
  if(n ^ 1) // Is it even?
    return 0;

  int max = static_cast<int>(sqrt(n));
  for(int i = 3; i <= max; i += 2)
  {
    if(n % i == 0)
      return false;
  }
  return true;
}

---

The other thing to do, if you could store large integers (i.e. you have a large integer class), and you have an upper bound for the numbers you'll be using, find all the primes in this range with the deterministic method above (this algorithm assumes that your desired integer will be sufficiently large to make storing these infeasible), compute their product, p, and then when you go to test a number, use Euclid's algorithm to test relative primality. This is a much more efficient algorithm provided the number of tests for primality later in your program is sufficient to warrant the compute time of finding them all to begin with.

There are also a number of probabalistic algorithms for determining primality, which you might want to try.

As an example, a^p = a (mod p) for any prime p (where ^ denotes exponentiation). So, if you are testing t, and choose a at random, if a^t = a (mod t) then t might be prime. On the other hand, if a^t != a (mod t), then t is definitely not prime. Several randomly chosen values of a give a pretty good probability that t is prime if it passes for all values.

instead of using these headers

Code:

---

#include<iostream.h>
#include<iomanip.h>
#include<stdlib.h>
#include<time.h>
#include<fstream.h>
#include<math.h>

---

use these

Code:

---

#include<iostream>
#include<iomanip>
#include<cstdlib>
#include<ctime>
#include<cfstream>
#include<cmath>

---

cfstream? Oh, I think not. That library is just <fstream> just like <iostream>.

yea your right - forgot about that one..

these are the C++ standard library header files

cassert
cctype
cfloat
climits
cmath
cstdlib
cstdio
cstring
ctime
iostream
iomanip
fstream
utility

any others that I missed??

These are the headers that my library implementation includes.

Quote:

---

The Standard C++ library consists of 51 required headers. This implementation also includes three additional headers, <hash_map>, <hash_set>, and <slist>, not required by the C++ Standard, for a total of 54 headers. Of these 54 headers, 16 constitute the Standard Template Library, or STL. These are indicated below with the notation (STL):

<algorithm> -- (STL) for defining numerous templates that implement useful algorithms
<bitset> -- for defining a template class that administers sets of bits
<complex> -- for defining a template class that supports complex arithmetic
<deque> -- (STL) for defining a template class that implements a deque container
<exception> -- for defining several functions that control exception handling
<fstream> -- for defining several iostreams template classes that manipulate exteral files
<functional> -- (STL) for defining several templates that help construct predicates for the templates defined in <algorithm> and <numeric>
<map> -- (STL) for defining template classes that implement hashed associative containers that map keys to values
<hash_set> -- (STL) for defining template classes that implement hashed associative containers
<iomanip> -- for declaring several iostreams manipulators that take an argument
<ios> -- for defining the template class that serves as the base for many iostreams classes
<iosfwd> -- for declaring several iostreams template classes before they are necessarily defined
<iostream> -- for declaring the iostreams objects that manipulate the standard streams
<istream> -- for defining the template class that performs extractions
<iterator> -- (STL) for defining several templates that help define and manipulate iterators
<limits> -- for testing numeric type properties
<list> -- (STL) for defining a template class that implements a doubly linked list container
<locale> -- for defining several classes and templates that control locale-specific behavior, as in the iostreams classes
<map> -- (STL) for defining template classes that implement associative containers that map keys to values
<memory> -- (STL) for defining several templates that allocate and free storage for various container classes
<new> -- for declaring several functions that allocate and free storage
<numeric> -- (STL) for defining several templates that implement useful numeric functions
<ostream> -- for defining the template class that performs insertions
<queue> -- (STL) for defining a template class that implements a queue container
<set> -- (STL) for defining template classes that implement associative containers
<slist> -- (STL) for defining a template class that implements a singly linked list container
<sstream> -- for defining several iostreams template classes that manipulate string containers
<stack> -- (STL) for defining a template class that implements a stack container
<stdexcept> -- for defining several classes useful for reporting exceptions
<streambuf> -- for defining template classes that buffer iostreams operations
<string> -- for defining a template class that implements a string container
<strstream> -- for defining several iostreams classes that manipulate in-memory character sequences
<typeinfo> -- for defining class type_info, the result of the typeid operator
<utility> -- (STL) for defining several templates of general utility
<valarray> -- for defining several classes and template classes that support value-oriented arrays
<vector> -- (STL) for defining a template class that implements a vector container

The Standard C++ library works in conjunction with the 18 headers from the Standard C library, sometimes with small alterations. The headers come in two forms, new and traditional. The new-form headers are:

<cassert> -- for enforcing assertions when functions execute
<cctype> -- for classifying characters
<cerrno> -- for testing error codes reported by library functions
<cfloat> -- for testing floating-point type properties
<ciso646> -- for programming in ISO 646 variant character sets
<climits> -- for testing integer type properties
<clocale> -- for adapting to different cultural conventions
<cmath> -- for computing common mathematical functions
<csetjmp> -- for executing nonlocal goto statements
<csignal> -- for controlling various exceptional conditions
<cstdarg> -- for accessing a varying number of arguments
<cstddef> -- for defining several useful types and macros
<cstdio> -- for performing input and output
<cstdlib> -- for performing a variety of operations
<cstring> -- for manipulating several kinds of strings
<ctime> -- for converting between various time and date formats
<cwchar> -- for manipulating wide streams and several kinds of strings
<cwctype> -- for classifying wide characters

---

Note that it also includes the following deprecated standard C library headers and the old non-standard C++ library headers.

Quote:

---

The traditional Standard C library headers are:

<assert.h> -- for enforcing assertions when functions execute
<ctype.h> -- for classifying characters
<errno.h> -- for testing error codes reported by library functions
<float.h> -- for testing floating-point type properties
<iso646.h> -- for programming in ISO 646 variant character sets
<limits.h> -- for testing integer type properties
<locale.h> -- for adapting to different cultural conventions
<math.h> -- for computing common mathematical functions
<setjmp.h> -- for executing nonlocal goto statements
<signal.h> -- for controlling various exceptional conditions
<stdarg.h> -- for accessing a varying number of arguments
<stddef.h> -- for defining several useful types and macros
<stdio.h> -- for performing input and output
<stdlib.h> -- for performing a variety of operations
<string.h> -- for manipulating several kinds of strings
<time.h> -- for converting between various time and date formats
<wchar.h> -- for manipulating wide streams and several kinds of strings
<wctype.h> -- for classifying wide characters

Finally, in this implementation, the Standard C++ library also includes several headers for compatibility with traditional C++ libraries:

<fstream.h> -- for defining several iostreams template classes that manipulate exteral files
<iomanip.h> -- for declaring several iostreams manipulators that take an argument
<iostream.h> -- for declaring the iostreams objects that manipulate the standard streams
<new.h> -- for declaring several functions that allocate and free storage
<stl.h> -- for declaring several template classes that aid migration from older versions of the Standard Template Library

---