Analysis Software
Documentation for
sPHENIX
simulation software
Home page
Related Pages
Modules
Namespaces
Classes
Files
Examples
External Links
File List
File Members
All
Classes
Namespaces
Files
Functions
Variables
Typedefs
Enumerations
Enumerator
Friends
Macros
Groups
Pages
prime_tables.h
Go to the documentation of this file.
Or view
the newest version in sPHENIX GitHub for file prime_tables.h
1
// Copyright 2008 Google Inc.
2
// All Rights Reserved.
3
//
4
// Redistribution and use in source and binary forms, with or without
5
// modification, are permitted provided that the following conditions are
6
// met:
7
//
8
// * Redistributions of source code must retain the above copyright
9
// notice, this list of conditions and the following disclaimer.
10
// * Redistributions in binary form must reproduce the above
11
// copyright notice, this list of conditions and the following disclaimer
12
// in the documentation and/or other materials provided with the
13
// distribution.
14
// * Neither the name of Google Inc. nor the names of its
15
// contributors may be used to endorse or promote products derived from
16
// this software without specific prior written permission.
17
//
18
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
21
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
22
// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
23
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
24
// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29
//
30
// Author: wan@google.com (Zhanyong Wan)
31
// Author: vladl@google.com (Vlad Losev)
32
33
// This provides interface PrimeTable that determines whether a number is a
34
// prime and determines a next prime number. This interface is used
35
// in Google Test samples demonstrating use of parameterized tests.
36
37
#ifndef GTEST_SAMPLES_PRIME_TABLES_H_
38
#define GTEST_SAMPLES_PRIME_TABLES_H_
39
40
#include <algorithm>
41
42
// The prime table interface.
43
class
PrimeTable
{
44
public
:
45
virtual
~PrimeTable
() {}
46
47
// Returns true iff n is a prime number.
48
virtual
bool
IsPrime
(
int
n
)
const
= 0;
49
50
// Returns the smallest prime number greater than p; or returns -1
51
// if the next prime is beyond the capacity of the table.
52
virtual
int
GetNextPrime
(
int
p
)
const
= 0;
53
};
54
55
// Implementation #1 calculates the primes on-the-fly.
56
class
OnTheFlyPrimeTable
:
public
PrimeTable
{
57
public
:
58
virtual
bool
IsPrime
(
int
n
)
const
{
59
if
(n <= 1)
return
false
;
60
61
for
(
int
i
= 2;
i
*
i
<=
n
; i++) {
62
// n is divisible by an integer other than 1 and itself.
63
if
((n % i) == 0)
return
false
;
64
}
65
66
return
true
;
67
}
68
69
virtual
int
GetNextPrime
(
int
p
)
const
{
70
for
(
int
n
= p + 1;
n
> 0;
n
++) {
71
if
(
IsPrime
(
n
))
return
n
;
72
}
73
74
return
-1;
75
}
76
};
77
78
// Implementation #2 pre-calculates the primes and stores the result
79
// in an array.
80
class
PreCalculatedPrimeTable
:
public
PrimeTable
{
81
public
:
82
// 'max' specifies the maximum number the prime table holds.
83
explicit
PreCalculatedPrimeTable
(
int
max)
84
:
is_prime_size_
(max + 1),
is_prime_
(new bool[max + 1]) {
85
CalculatePrimesUpTo
(max);
86
}
87
virtual
~PreCalculatedPrimeTable
() {
delete
[]
is_prime_
; }
88
89
virtual
bool
IsPrime
(
int
n
)
const
{
90
return
0 <= n && n <
is_prime_size_
&&
is_prime_
[
n
];
91
}
92
93
virtual
int
GetNextPrime
(
int
p
)
const
{
94
for
(
int
n
= p + 1;
n
<
is_prime_size_
;
n
++) {
95
if
(
is_prime_
[
n
])
return
n
;
96
}
97
98
return
-1;
99
}
100
101
private
:
102
void
CalculatePrimesUpTo
(
int
max) {
103
::std::fill(
is_prime_
,
is_prime_
+
is_prime_size_
,
true
);
104
is_prime_
[0] =
is_prime_
[1] =
false
;
105
106
for
(
int
i
= 2;
i
<= max;
i
++) {
107
if
(!
is_prime_
[
i
])
continue
;
108
109
// Marks all multiples of i (except i itself) as non-prime.
110
for
(
int
j
= 2*i;
j
<= max;
j
+=
i
) {
111
is_prime_
[
j
] =
false
;
112
}
113
}
114
}
115
116
const
int
is_prime_size_
;
117
bool
*
const
is_prime_
;
118
119
// Disables compiler warning "assignment operator could not be generated."
120
void
operator=
(
const
PreCalculatedPrimeTable
&
rhs
);
121
};
122
123
#endif // GTEST_SAMPLES_PRIME_TABLES_H_
JETSCAPE
blob
main
external_packages
googletest
googletest
samples
prime_tables.h
Built by
Jin Huang
. updated:
Sat Feb 17 2024 22:18:22
using
1.8.2 with
sPHENIX GitHub integration