-
Notifications
You must be signed in to change notification settings - Fork 2
/
Composite number generation.cpp
89 lines (71 loc) · 1.83 KB
/
Composite number generation.cpp
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
//#Name: Anonta Haque #Problm: generate Composite numbers
// Using sieve of eratosthenes algorithm
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long L; //"%ld"
typedef long long LL; //"%lld"
typedef long double LD; //"%f"
typedef unsigned int UI; // "%u"
typedef unsigned long UL; //"%lu"
typedef unsigned long long ULL; //"%llu"
short COUNT_;
#define sf scanf
#define pf printf
#define NL pf("\n");
#define SS pf(">_<LOOOOOK@MEEEEEEEEEEEEEEE<<( %d )>>\n",++COUNT_);
#define DD(x_) cout<<">>>>( "<<++COUNT_<<" ) "<<#x_<<": "<<x_<<endl;
#define arySZ(x_) sizeof(x_)/sizeof(x_[0]) //(array must be in scope)
//constants
const int SZ= 1E6;
int pr[8];
bool stat[SZ+10];
int composites[SZ+10];
//Sieve of eratosthenes, generate and store composite numbers
// in composites array
void sieve(LL N)
{
// int composite_count= 3;
//safety check
if(N >= arySZ(stat) || N >= arySZ(composites)){
pf("Array to short!!!\n");
return;
}
//create array for marking composite numbers
// mark all odd composite numbers in the stat array
// corresponding to index number
LL sqn= sqrt((double)N);
for(int i= 3; i<=sqn; i+= 2)
{
//if not marked as odd composite yet
if(stat[i] == 0)
{
for(int j= i*i; j<=N; j+= i<<1)
{
stat[j]= 1;
}
}
}
//fill int the first 3 elements
composites[0]= 4;
composites[1]= 6;
composites[2]= 8;
for(int i= 9, j= 3; i<N; i+=2)
{
if(stat[i] == 1)
{
// pf("%d ", i);
composites[j]= i;
j++;
}
// pf("%d ", i+1);
composites[j]= i+1;
j++;
}
}
int main(void)
{
sieve(1e6);
return 0;
}