C++素数库
C++素数库
提问于 2016-06-30 19:08:34
这个素数库是我在c++中完成的首批编程项目之一。我的目标是创建一个有效的way.Note中处理素数的有用函数：(所使用的大部分函数都是由Atkin的筛子驱动的)
我想知道任何类型的优化或更好的代码实践，我应该改变或合并到我的项目，任何帮助是非常感谢的。
职能：
- pn_find(n)：发现最大素数小于或等于给定的输入。
- pn_count( n)：计算给定数(包括n)下素数的数量。
- pn_den( h )：计算素数从1到h的密度。
- pn_test(a)：一个数字的素数测试，返回一个布尔值(1如果是素数，0不是素数)。
- pn_twin(a)：测试给定的数字是否是孪生素数，返回一个布尔值(如果它是孪生素数，则返回1；如果它不是孪生素数，则返回0)。
- pn_cousin(a)：测试给定的数字是否是表亲素数，返回一个布尔值(如果它是表亲素数，则返回0)。
- pn_sexy(a)：测试给定的数字是否是性感素数，返回一个布尔值(如果它是性感素数，则返回0)。
- pn_pal( n )：发现最高回文素数等于或小于n。
- n_fac(f)：求给定数的最高素数。
- n_cfac( f)：计算构成数字(包括f)的素数数。
hpp档案：
#ifndef inpalprime_hpp
#define inpalprime_hpp
#include <vector>
#include <string>
class inpalprime
{
public:
long long pn_find(long long n);
long long pn_count(long long n);
long double pn_den(long double h);
bool pn_test(long long a);
bool pn_twin(long long a);
bool pn_cousin(long long a);
bool pn_sexy(long long a);
long long pn_pal(long long n);
long long n_fac(long long f);
long long n_cfac(long long f);
private:
std::vector<bool> atkinsieve(long long m);
std::vector<long long> factorizer(long long f);
bool pal_test(long long n);
long long maxprime;
long long primecount;
long double primeden;
long long pal;
std::string rev;
long long maxfac;
long long cfac;
};
#endif /* inpalprime_hpp */cpp文件：
#include "inpalprime.hpp"
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>
long long inpalprime::pn_find(long long n)
{
auto p_find=atkinsieve(n);
//finds the highest possible prime less or equal to n
for(std::vector<bool>::size_type it=p_find.size(); it!=1; it--)
{
if(p_find[it])
{
maxprime=it;
break;
}
}
return maxprime;
}
long long inpalprime::pn_count(long long n)
{
auto p_count=atkinsieve(n);
//counts the number of primes less or equal to n
primecount=std::count(p_count.begin(), p_count.end(), true);
return primecount;
}
long double inpalprime::pn_den(long double h)
{
//calculates density of primes from 1 to h
primeden=(pn_count(h)/h);
return primeden;
}
bool inpalprime::pn_test(long long a)
{
//primality test based on the sieve of atkin
if(a!=pn_find(a))
{
return false;
}
return true;
}
bool inpalprime::pn_twin(long long a)
{
auto p_tw=atkinsieve(a+2);
if(a==2)
{
return false;
}
//checks if a+2 or a-2 is also prime
else if(p_tw[p_tw.size()-3] && (p_tw[p_tw.size()-1] || p_tw[p_tw.size()-5]))
{
return true;
}
return false;
}
bool inpalprime::pn_cousin(long long a)
{
auto p_co=atkinsieve(a+4);
if(a==2)
{
return false;
}
//checks if a+4 or a-4 is also prime
else if(p_co[p_co.size()-5] && (p_co[p_co.size()-1] || p_co[p_co.size()-9]))
{
return true;
}
return false;
}
bool inpalprime::pn_sexy(long long a)
{
auto p_se=atkinsieve(a+6);
if(a==2 || a==3)
{
return false;
}
//checks if a+6 or a-6 is also prime
else if(p_se[p_se.size()-7] && (p_se[p_se.size()-1] || p_se[p_se.size()-13]))
{
return true;
}
return false;
}
long long inpalprime::pn_pal(long long n)
{
auto p_pal=atkinsieve(n);
//finds the highest palindromic prime less or equal to n
for(std::vector<bool>::size_type it=p_pal.size(); it!=1; it--)
{
if(p_pal[it] && pal_test(it))
{
pal=it;
break;
}
}
return pal;
}
long long inpalprime::n_fac(long long f)
{
//finds the highest prime factor less or equal to f
maxfac=factorizer(f).back();
return maxfac;
}
long long inpalprime::n_cfac(long long f)
{
//counts the number of prime factors that compose f, if f is prime the returned value is 1
cfac=factorizer(f).size();
return cfac;
}
std::vector<bool> inpalprime::atkinsieve(long long m)
{
std::vector<bool> p_test(m+1, false);
//defines square root of m
unsigned long long root=ceil(sqrt(m));
//sieve axioms
for(unsigned long long x=1; x<=root; x++)
{
for(long long y=1; y<=root; y++)
{
long long i=(4*x*x)+(y*y);
if (i<=m && (i%12==1 || i%12==5))
{
p_test[i].flip();
}
i=(3*x*x)+(y*y);
if(i<=m && i%12==7)
{
p_test[i].flip();
}
i=(3*x*x)-(y*y);
if(x>y && i<=m && i%12==11)
{
p_test[i].flip();
}
}
}
//marks 2,3,5 and 7 as prime numbers
p_test[2]=p_test[3]=p_test[5]=p_test[7]=true;
//marks all multiples of primes as non primes
for(long long r=5; r<=root; r++)
{
if((p_test[r]))
{
for(long long j=r*r; j<=m; j+=r*r)
{
p_test[j]=false;
}
}
}
return p_test;
}
std::vector<long long> inpalprime::factorizer(long long f)
{
std::vector<long long> p_fac;
long long p=3;
//removes factors of 2
while(f%2==0)
{
p_fac.push_back(2);
f=f/2;
}
//finds prime factors of f
while(f!=1)
{
while(f%p==0)
{
p_fac.push_back(p);
f=f/p;
}
p+=2;
}
return p_fac;
}
bool inpalprime::pal_test(long long n)
{
//converts n to a string
rev=std::to_string(n);
//checks if the reverse of rev is equal to rev
for(int i=0; i<rev.size()/2; i++)
{
if(rev[i]!=rev[rev.size()-1-i])
{
return false;
}
}
return true;
}回答 1
Code Review用户
回答已采纳
发布于 2016-06-30 23:32:58
首先，您的格式非常奇怪。不确定您的代码是否是这样的，或者它是否只是复制粘贴的伪制品，但是无论哪种方式，您都应该清理它。
其次，每当我在pn_***中看到像C++这样的前缀时，我都会畏缩。我可以在C中忍受，因为有时没有什么可以避免碰撞的。但是在C++中，我们有类和名称空间，使用其中一种或另一种应该没有必要这样做。在这种情况下，我并没有真正看到使用类的理由(为什么我必须创建一个新的inpalprime才能完成这些方法？)因此，要么使所有内容都是静态的，要么使用命名空间。我要选择一个命名空间。
第三，你们的名字糟透了。他们真的很难理解。我把它们重命名为这样
pn_find -> largest_prime
pn_count -> count_primes
pn_den -> prime_density
pn_test -> is_prime
pn_twin -> is_twin_prime
pn_cousin -> is_cousin_prime
pn_sexy -> is_sexy_prime
pn_pal -> largest_palindromic_prime
n_fac -> largest_prime_factor
n_cfac -> count_prime_factors
atkinsieve -> get_primes
factorizer -> get_prime_factors
pal_test -> is_palindrome至少对我来说，这些都是在可读性方面的巨大改进，而且其中一些至少更好一些。
State
我真的不明白为什么这么多这样的国家-它使它很难读，而且没有一个明显的理由。其中一些也没有得到适当的初始化，这可能会导致一些令人惊讶的行为。
pn_find (largest_prime)
只需在这里使用迭代器，然后返回而不是breaking。这会让事情变得更简单。在此之后，使用find变得非常简单。目前还不清楚在错误情况下应该返回什么(即，如果没有找到素数)，所以我让它取消引用end。并不理想，但请确保指定使用无效的n是未定义的行为。否则，如果n无效，您可以添加一个检查以返回某些默认值。
pn_test (is_prime)
你可以在这里简化很多。只需将比较(!=与==)反转，然后返回结果。
pn_twin，pn_cousin，pn_sexy (is_twin_prime，is_cousin_prime，is_sexy_prime)
只需将所有的布尔值加在一起，并返回结果。干净多了。
除此之外，不同计算的实现似乎并不可怕。有可能真正拖慢你的是你重新计算所有的素数，每一次。因素也一样。如果在这两个函数中添加某种缓存/回忆法(或改进的算法)，那么您将做得更好。另外，在向量上使用push_back是非常糟糕的--你将malloc赶出这个动物园，这会很快地减慢速度。试着先预留足够的空间(这很难，但你可能会想出一个像样的度量)，然后你的推回就不会失去任何东西，直到它们填满你的向量。您的is_palindrome函数可以很容易地线程化，以获得较小的速度增益。
这就是我最后想出来的
inpalprime.hpp
#ifndef inpalprime_hpp
#define inpalprime_hpp
#include <vector>
#include <string>
namespace inpalprime {
std::vector<bool> get_primes(long long m);
std::vector<long long> get_prime_factors(long long f);
bool is_palindrome(long long n);
long long largest_prime(long long n);
long long count_primes(long long n);
long double prime_density(long double h);
bool is_prime(long long p);
bool is_twin_prime(long long p);
bool is_cousin_prime(long long p);
bool is_sexy_prime(long long p);
long long largest_palindromic_prime(long long n);
long long largest_prime_factor(long long f);
long long count_prime_factors(long long f);
}
#endif // defined inpalprime_hppinpalprime.cpp
#include "inpalprime.hpp"
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>
long long inpalprime::largest_prime(long long n)
{
auto primes = get_primes(n);
auto it = std::find(primes.rbegin(), primes.rend(), true);
return primes.size() - std::distance(primes.rbegin(), it);
}
long long inpalprime::count_primes(long long n)
{
auto primes = get_primes(n);
return std::count(primes.begin(), primes.end(), true);
}
long double inpalprime::prime_density(long double h)
{
return count_primes(h) / h;
}
bool inpalprime::is_prime(long long a)
{
return a == largest_prime(a);
}
bool inpalprime::is_twin_prime(long long a)
{
auto primes = get_primes(a + 2);
return a != 2
&& primes[primes.size()-3]
&& (primes[primes.size()-1] || primes[primes.size()-5]);
}
bool inpalprime::is_cousin_prime(long long a)
{
auto primes = get_primes(a + 4);
return a != 2
&& primes[primes.size()-5]
&& (primes[primes.size()-1] || primes[primes.size()-9]);
}
bool inpalprime::is_sexy_prime(long long a)
{
auto primes = get_primes(a + 6);
return (a != 2 && a != 3)
&& primes[primes.size() - 7]
&& (primes[primes.size() - 1] || primes[primes.size() - 13]);
}
long long inpalprime::largest_palindromic_prime(long long n)
{
auto primes = get_primes(n);
auto it = std::find_if(primes.rbegin(), primes.rend(), [&](auto it) {
auto num = primes.size() - std::distance(primes.rbegin(), it)
return *it && is_palindrome(num);
});
return primes.size() - std::distance(primes.rbegin(), it);
}
long long inpalprime::largest_prime_factor(long long f)
{
return get_prime_factors(f).back();
}
long long inpalprime::count_prime_factors(long long f)
{
return get_prime_factors(f).size();
}
std::vector<bool> inpalprime::get_primes(long long m)
{
std::vector<bool> p_test(m+1, false);
//defines square root of m
unsigned long long root=ceil(sqrt(m));
//sieve axioms
for(unsigned long long x=1; x<=root; x++)
{
for(long long y=1; y<=root; y++)
{
long long i=(4*x*x)+(y*y);
if (i<=m && (i%12==1 || i%12==5))
{
p_test[i].flip();
}
i=(3*x*x)+(y*y);
if(i<=m && i%12==7)
{
p_test[i].flip();
}
i=(3*x*x)-(y*y);
if(x>y && i<=m && i%12==11)
{
p_test[i].flip();
}
}
}
//marks 2,3,5 and 7 as prime numbers
p_test[2]=p_test[3]=p_test[5]=p_test[7]=true;
//marks all multiples of primes as non primes
for(long long r=5; r<=root; r++)
{
if((p_test[r]))
{
for(long long j=r*r; j<=m; j+=r*r)
{
p_test[j]=false;
}
}
}
return p_test;
}
std::vector<long long> inpalprime::get_prime_factors(long long f)
{
std::vector<long long> p_fac;
long long p=3;
//removes factors of 2
while(f%2==0)
{
p_fac.push_back(2);
f=f/2;
}
//finds prime factors of f
while(f!=1)
{
while(f%p==0)
{
p_fac.push_back(p);
f=f/p;
}
p+=2;
}
return p_fac;
}
bool inpalprime::is_palindrome(long long n)
{
//converts n to a string
std::string rev = std::to_string(n);
//checks if the reverse of rev is equal to rev
for(int i=0; i<rev.size()/2; i++)
{
if(rev[i]!=rev[rev.size()-1-i])
{
return false;
}
}
return true;
}页面原文内容由Code Review提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://codereview.stackexchange.com/questions/133520
复制相关文章
相似问题
腾讯云开发者
