C++

Forum

 
 
sieve analysis

mrniceguy420 (6)
Hey Guys,

i have written a program to find prime numbers by sieve process. My problem is that for example prime number 73 is 65537, which is a prime number, but in the wrong order. This comes with a period of numbers where just wrong is stored. If you have a suggestion i would be grateful.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
 
//
//  main.cpp
//  Primes
//
//  Created by Lukas Adam on 20.12.14.
//  Copyright (c) 2014 Lukas Adam. All rights reserved.
//
#include <unordered_map>
#include <map>
#include <iostream>
#include <string>
#include <fstream>
#include <time.h>
#define N 10000
#define fileName "Prims.data"

using namespace std;

typedef multimap<unsigned int, unsigned int> umm;
typedef multimap<unsigned int, unsigned int>::value_type myPair;

bool isPrime(unsigned int);
void write_Data(umm&);
void write_String(string);

int main(void) {
    
    time_t begin, end;
    unsigned int count = 0;
    umm prime;
    cout << "Calculating Primes" << endl;
    //Starte Zeitmessung
    time(&begin);
    //Sieveprocess
    for(int i = 2; count < N; ++i){
        umm::iterator it = prime.find(i);
        if(it != prime.end()){                        //If i is equal to a multiple of any found primenumber
            unsigned int key = it->first + it->second;//Save Key Value and add Prime for next relevant multiple
            unsigned int val = it->second;            //Save primenumber
            prime.erase(it);                          //Delete old Entry
            prime.insert(myPair(key, val));           //Insert new Entry
        } else if(isPrime(i)){                        //else check if i is primenumber
            prime.insert(myPair(i*i, i));             //Insert i with key i^2
            ++count;
        }
    }
    //Beende Zeitmessung
    time(&end);
    write_Data(prime);
    double diff = difftime(end, begin);
    write_String("Calculationtime " + to_string(diff) + "s");
    cout << "Finished" << endl;
    
    return 0;
} //End Main

/**
 * Checks if parameter p is a primenumber
 */
bool isPrime(unsigned int p){
   for(int i = 2; i < (p / 2) + 1; i++)
        if(p % i == 0)
            return false;
    
    return true;
}
/**
 * Writes the multimap on a Textfile
 */
void write_Data(umm& data){
    ofstream datei(fileName);
    if(!datei.is_open()){
        cout << "Error on writing file" << endl;
    } else {
        unsigned int count = 0;
        for(auto x: data)
            datei << ++count << ": {" << x.second << "}   multiple:" << x.first << "\n";
    }
    datei.close();
}

/**
 * Writes a single string on a textfile
 * ios::app option for start writing at the end of the file
 * so things dont get overwritten
 */
void write_String(string s){
    ofstream datei(fileName, ios::app);
    if(!datei.is_open()){
        cout << "Error on writing file" << endl;
    } else {
        datei << s << "\n";
    }
    datei.close();
}
Last edited on
norm b (337)
Hint: 652372 is too large to be stored in an int or uint.


Edit: added uint
Last edited on
mrniceguy420 (6)
Oh well ok that explains much :)) thank you.
Topic archived. No new replies allowed.