primes.cpp

来自「realview22.rar」· C++ 代码 · 共 156 行

//**************************************************************
// Prime Number Generator 3.2
//
// Copyright (C) ARM Limited 1999-2002. All rights reserved.
//**************************************************************

// Calculate the nth prime number and display it, and the time 
// taken to calculate it.

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

#if __ARMCC_VERSION >= 200000
using namespace std;
#endif

// Prime Number Calculating Function
int CalculatePrimes(vector<int,allocator<int> > prime_numbers, 
                                        int prime_count, int goal, double &Time)
{
        int square;
        int number =39;
        int remainder;
        int root = 1;
        int prime;
        clock_t Start, Finish;
                
        // Start timer
        Start = clock();
                        
        while(prime_count < goal)
        {
                square = root * root;
                
                while(number > square)
                {
                        root++;
                        square = root * root;
                }
                
                for(int i=0; i < prime_count; i++)
                {
                        prime = prime_numbers[i];
                        
                        if (prime > root)
                        {
                                square = prime_count;
                                prime_numbers[square--] = number;
                                prime_count++;
                                break;
                        }
                
                        remainder = number % prime;
        
                        if (remainder == 0) 
                        {
                                //if not prime ditch number
                                break;
                        }
                }                       
                number = number + 2;
        }
        
        Finish = clock();
        
        // Calculate time taken
        Time = (double)(Finish - Start) / CLOCKS_PER_SEC;
        
        return prime_numbers[goal];
}


// Output Results Function
void OutputResults(int answer, int goal, double Time)
{
        // Output answer
        cout << "\n\nThe " << goal << "th prime number is: "
                  << answer
                  << "\n\nIt took " << Time << " seconds.";
                 
        // Debugging Information
        cout << "\n\nIf you are reading this message you have\n"
                  << "found the bug in the code!";
                 
        return;
}


//**************************************************************
// Main Program
//**************************************************************
int main(void)
{       
        int prime;
        int* answer;
        int prime_count=0;
        double Time;
        
        
        // Get data from user
        cout << "\n\nPrime Number Generator\n"
             <<"Which prime number do you wish to calculate? \n"
             << "(must be above 12): ";
        cin  >> prime;
        
        while (prime > 10000)
        {
                cout << "ERROR: There might not be enough memory available for"
                          << "\nthis many prime numbers, please choose a smaller value. \n";
                cin  >> prime;
        } 
        
        cout << "\nCalculating......";
        
        vector<int, allocator<int> > prime_numbers((prime + 1), -1);

        // Give it some to start off with
        prime_numbers[prime_count] = 2;
        prime_count++;
        prime_numbers[prime_count] = 3;
        prime_count++;
        prime_numbers[prime_count] = 5;
        prime_count++;
        prime_numbers[prime_count] = 7;
        prime_count++;
        prime_numbers[prime_count] = 11;
        prime_count++;
        prime_numbers[prime_count] = 13;
        prime_count++;
        prime_numbers[prime_count] = 17;
        prime_count++;
        prime_numbers[prime_count] = 19;
        prime_count++;
        prime_numbers[prime_count] = 23;
        prime_count++;
        prime_numbers[prime_count] = 29;
        prime_count++;
        prime_numbers[prime_count] = 31;
        prime_count++;
        prime_numbers[prime_count] = 37;
        prime_count++;
        
        // Calculate numbers
        answer = (int*) CalculatePrimes(prime_numbers, prime_count, prime, Time);
        
        // Call Output Function
        OutputResults(*answer, prime, Time);
        
        return 0;
}

// End of file