求一个序列，其中任意n个数字相加不会等于该序列里的其他值，任意一个数字的倍数不等于该序列里的其他值
/* 求一个序列，要求： 1.任意n个数字相加不会等于该序列里的其他值 2.任意一个数字的倍数不等于该序列里的其他值*/#include <iomanip>#include <iostream>#include <sstream>#include <string>#include <vector>using namespace std;string operator+(string const & s, int n){ ostringstream oss; oss << s << n; return oss.str();}class ExSieve{ vector<int> m_sieve; vector<int> m_prime; void clear() { m_sieve[0] = 0; // 0不影响第1条的判定。0的倍数总是0，满足第2条。 m_sieve[1] = 0; // 1乘后续的数都满足第2条，去掉。否则形不成序列 for(int i = 2, n = m_sieve.size(); i < n; ++i){ m_sieve[i] = 1; } }#ifdef dbg void accum_sieve(int i, int sum, string sum_list)#else void accum_sieve(int i, int sum)#endif { int t = sum + m_prime[i]; if(t < m_sieve.size() && m_sieve[t]){ m_sieve[t] = 0;#ifdef dbg cout << setw(10) << t << " = " << sum_list << ' ' << m_prime[i] << '\n';#endif } if(++i < m_prime.size()){#ifdef dbg accum_sieve(i, sum, sum_list); accum_sieve(i, t , sum_list + " " + m_prime[i-1]);#else accum_sieve(i, sum); accum_sieve(i, t );#endif } }public: ExSieve() : m_sieve(2), m_prime() { this->clear(); } void init(int n) { if(n < 2){ n = 2; } m_sieve.resize(n); m_prime.clear(); this->clear(); } void sieve() { this->clear(); for(int i = 2, nb = 0, CNT = m_sieve.size(); i < CNT; ++i){ if(m_sieve[i]){ for(int j = i + i; j < CNT; j += i){ // 倍数 if(m_sieve[j]){ m_sieve[j] = 0; } } if(!m_prime.empty()){#ifdef dbg accum_sieve(0, i, string("") + i);#else accum_sieve(0, i);#endif } m_prime.push_back(i); } } } void print() { for(int i = 0, n = m_prime.size(); i < n; ++i){ cout << m_prime[i] << ' '; } cout << '\n'; }};int main(){ ExSieve es; es.init(10000000); es.sieve(); es.print(); return 0;}
在我的电脑上过滤一千万以内的数，用了8.922s，还可以。
2 3 7 11 17 25 59 67 185 193 563 571 1697 1747 5141 5149 11995 25727 27439 78893 82345 240131 243583 723845 727297 2174987 2178439 6530119 6530123
要求2用筛法，改进余地不大。
继续考虑条件1，但很明显，递归求子序列和重复了多次，冗余。
若f(1)到f(n)所有子序列的和记为集合S(n)，那么S(n) 中的元素依次加上 f(n+1)，构成集合SS(n)，则S(n)与SS(n)的并集就是S(n+1)，这样避免了反复递归计算。
由此得到算法2，改进明显：筛选1千万以内的数只需 0.219s。筛选1亿以内的数也只需2秒。
#include <cstring>#include <iomanip>#include <iostream>#include <sstream>#include <string>#include <list>#include <vector>using namespace std;string operator+(string const & s, int n){ ostringstream oss; oss << s << n; return oss.str();}class ExSieve2{ vector<char> m_sums; vector<char> m_sieve; vector<int> m_sums_tmp; void init(int n) { if(n < 2){ n = 2; } m_sums.resize(n); m_sieve.resize(n); memset(&m_sums[0], 0, n); memset(&m_sieve[0], 0, n); m_sums[1] = 1; // 任何数都是1的倍数，有1就形不成序列。必须去掉。 m_sieve[0] = 1; m_sieve[1] = 1; }public: ExSieve2() : m_sums(), m_sieve(), m_sums_tmp() { } void sieve(int const n) { this->init(n); for(int i = 2, max_sum = 0; i < n; ++i){ if(m_sieve[i]){ continue; } for(int j = 2, k = 0, J = min(max_sum, n-i); j < J; ++j){ if(m_sums[j]){ // j是某个子序列的和、则(j + i)是子序列和。 k = j + i; if(m_sums[k] == 0){ m_sums_tmp.push_back(k); m_sieve[k] = 1; } } } for(vector<int>::const_iterator p = m_sums_tmp.begin(), e = m_sums_tmp.end(); p != e; ++p){ m_sums[*p] = 1; } m_sums_tmp.resize(0); for(int j = 2, k = 0, J = min(i, n-i); j < J; ++j){ if(m_sieve[j] == 0){ // j本身是序列中的元素，则(j + i)是子序列和。 k = j + i; if(m_sums[k] == 0){ m_sums [k] = 1; m_sieve[k] = 1; } } } max_sum += i; if(max_sum > 2 && max_sum < n){ m_sums[max_sum] = 1; m_sieve[max_sum] = 1; } for(int j = i + i; j < n; j += i){ // 倍数 if(m_sieve[j] == 0){ m_sieve[j] = 1; } } } } void print() { for(int i = 0, n = m_sieve.size(); i < n; ++i){ if(m_sieve[i] == 0){ cout << i << ' '; } } cout << '\n'; }};int main(){ ExSieve2 es; es.sieve(100000000); es.print(); return 0;}