我又来啦~还是纯素数问题！
#include<iostream>
#include<bitset>
#include<cmath>
#include<cstdio>
#define N 100000000
using namespace std;
bitset <N+1> p;
int main()
{
int i,j;
p.set();
p.reset(0),p.reset(1);
for(i=4; i<N; i+=2)
p.reset(i);
for(i=3; i<=10000; i+=2)
if(p.test(i))
for(j=i*i;j<p.size();j+=i*2)
p.reset(j);
for (i=11;i<N;i+=2)//筛纯素数。对于n位数，只验证n-1位数是否为纯素数
{
if (p.test(i))
{
if (i%10!=3&&i%10!=7) {p.reset(i);continue;}
int wei=0,m=i;
while(m) m/=10,wei++;
if (!p.test(i%(int)pow(10.0,wei-1))) p.reset(i);
}
}
while(cin>>i)
{
if (i==1) {cout<<"2\n3\n5\n7\n";continue;}
for (j=pow(10.0,i-1)+1;j<pow(10.0,i);j+=2)
if (p.test(j)) printf("%d\n",j);
}
return 0;
}
#include <iostream>
#include <cstring>
#include <ctime>
unsigned char primes[ 100000000 / 8];
int unset_flag( unsigned i )
{
primes[ i >> 3 ] &= ~ ( 1 << ( i & 0x07) );
}
int get_flag( int i )
{
return primes[ i >> 3] & ( 1 << ( i & 0x07) );
}
int prepare_primes()
{
unset_flag(0);
unset_flag(1);
for( int i = 2; i < 10000; ++ i)
{
if( get_flag(i))
{
for( int j = i + i; j < 100000000; j += i)
{
unset_flag(j);
}
}
}
}
int test_number( unsigned int value, unsigned int base )
{
int is_prime = 1;
do
{
is_prime = get_flag( value );
value %= base;
base /= 10;
}while( is_prime && (base > 0));
return is_prime;
}
void test( int n )
{
std::clock_t start = std::clock();
std::memset( primes, 0xFF, sizeof(primes));
prepare_primes();
int begin = 10,end = 100;
for( int i = 2; i <= n; ++ i)
{
for( int value = begin; value < end; ++ value)
{
if( test_number(value, begin))
{
std::cout << value << ' ';
}
}
begin = end;
end *= 10;
}
std::cout << "\nTime: " << double(std::clock() - start)/CLOCKS_PER_SEC ;
}
int main()
{
test(8);
return 0;
}
