240
edits
Changes
→PHASE 1
----
=== Prime Numbers ===
Script started on Fri 10 Feb 2017 12:21:37 AM EST
hli206@matrix:~/GPU610/Assignment/primeNum> cat primeNum.custom.cpp
#include<iostream>
#include<ctime>
#include<chrono>
#include<cstdlib>
#include<math.h> // Math.h For sqrt function
using namespace std;
using namespace std::chrono;
void init(float* a, int n) {
const float randf = 1.0f / (float) RAND_MAX;
for (int i = 0; i < n; i++)
a[i] = std::rand() * randf;
}
void reportTime(const char* msg, steady_clock::duration span) {
auto ms = duration_cast<milliseconds>(span);
std::cout << msg << " - took - " <<
ms.count() << " millisecs" << std::endl;
}
void primeFinder(int num, int bn) {
for (int i=2; i<num; i++)
for (int j=2; j*j<=i; j++)
{
if (i % j == 0)
break;
else if (j+1 > sqrt(i)) {
if(bn == 1)
cout << i << endl;
}
}
}
int main() {
int n, boolN;
steady_clock::time_point ts, te;
cout<<"Enter the Number :";
cin>>n;
cout<<"Show result?(1/0)"<<endl;
cin>>boolN;
cout<<"List Of Prime Numbers Below "<<n<<endl;
std::srand(std::time(nullptr));
ts = steady_clock::now();
primeFinder(n, boolN);
te = steady_clock::now();
reportTime("Prime Number(); ", te - ts);
return 0;
}
hli206@matrix:~/GPU610/Assignment/primeNum> cat Makefile
# Makefile for Assignment1
#
VER=custom
GCC_VERSION = 5.2.0
PREFIX = /usr/local/gcc/${GCC_VERSION}/bin/
CC = ${PREFIX}gcc
CPP = ${PREFIX}g++
primeNum.${VER}: primeNum.${VER}.o
$(CPP) -oprimeNum.${VER} primeNum.${VER}.o
primeNum.${VER}.o: primeNum.${VER}.cpp
$(CPP) -c -O2 -std=c++14 primeNum.${VER}.cpp
clean:
rm *.o
hli206@matrix:~/GPU610/Assignment/primeNum> make
make: `primeNum.custom' is up to date.
hli206@matrix:~/GPU610/Assignment/primeNum> primeNum.custom
Enter the Number :50
Show result?(1/0)
1
List Of Prime Numbers Below 50
5
7
11
13
17
19
23
29
31
37
41
43
47
Prime Number(); - took - 0 millisecs
hli206@matrix:~/GPU610/Assignment/primeNum> primeNum.custom
Enter the Number :100000
Show result?(1/0)
0
List Of Prime Numbers Below 100000
Prime Number(); - took - 84 millisecs
hli206@matrix:~/GPU610/Assignment/primeNum> primeNum.custom
Enter the Number :1000000
Show result?(1/0)
0
List Of Prime Numbers Below 1000000
Prime Number(); - took - 2065 millisecs
hli206@matrix:~/GPU610/Assignment/primeNum> primNum.custom
If 'primNum.custom' is not a typo you can use command-not-found to lookup the package that contains it, like this:
cnf primNum.custom
hli206@matrix:~/GPU610/Assignment/primeNum> primeNum.custom
Enter the Number :10000000
Show result?(1/0)
0
List Of Prime Numbers Below 10000000
Prime Number(); - took - 53504 millisecs
hli206@matrix:~/GPU610/Assignment/primeNum> exit
exit
Script done on Fri 10 Feb 2017 12:25:53 AM EST
Analysis
This is a simple c++ program for finding any prime number within range. The program function primeFinder () is the only function in the program so it takes up to nearly 100% of the execution time. Moreover, primeFinder() has a runtime of O(n^2).
primeFinder() function:
void primeFinder(int num, int bn) {
for (int i=2; i<num; i++)
for (int j=2; j*j<=i; j++)
{
if (i % j == 0)
break;
else if (j+1 > sqrt(i)) {
if(bn == 1)
cout << i << endl;
}
}
}
== PHASE 2 ==
== PHASE 3 ==