1098: 素MM
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 52 Solved: 30
[Submit][Status][Web Board]
Description
素数有很多神奇的性质，所以很美。我们知道一个日期将年、月、日按顺序连接在一起可以组成一个八位数，例如2011年3月6日可以写成20110306。我的某个MM的生日组成的数是一个素数。偶尔我叫她素MM，没人知道是啥意思，她自己也不知道。O(∩_∩)O哈哈~我心里可是真的美美的(⊙o⊙)哦！
嗯，什么？你的生日也是素数？你也想做“素MM”或者“素GG”？那好吧，不过我可是很小气的哦！只有你出生在1988年或者1989年我才让你做“素MM”或“素GG”。要不然，你把这两年里日期组成的数是素数的找出来也可以——没准还带你到浙大去“旅游”呢！
Input
无
Output
1988年与1989年，这两年里的日期所组成的素数。每个素数占一行。
Sample Input
Sample Output
19880101
19880111
19880117
19880129
19880221
110ms多。。
#include <stdio.h>
#include <string.h>
#include <math.h>
int dp[55500] = { 0 };
int p[20000];
int dx[100000] = {0};
const int inf = sqrt ( 19891231);
int m[13] = {0,31,29,31,30,31,30,31,31,30,31,30,31};
void debug( )
{
#ifdef P
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
}
int fun(int year )
{
int temp, mon, day;
temp = year % 10000;
mon = temp / 100;
day = temp % 100;
if ( mon > 12 || mon <= 0 )
return 0;
else if ( day > m[mon] || day <= 0)
return 0;
else
return 1;
}
int main( )
{
debug( );
int i, j, n1, n2 = 0, k = 0;
n1 = sqrt(inf);
for ( i = 3; i <= n1; i += 2 ) {
if (dp[i / 2] )
continue;
for ( j = i * i; j <= inf; j += i + i)
dp[j / 2] = 1;
}
p[0] = 2;
k = 1;
for ( i = 1; i < (inf+1) / 2; i++)
if (!dp[i])
p[k++] = 2 * i + 1;
for ( i= 0; i < k; i++)
for ( j = p[i] + p[i] ; j <= 19891231; j += p[i] )
if (j - 19880100 > 0)
dx[j-19880100] = 1;
for ( i = 0 ; i <= 11131 ; i++)
if (dx[i] != 1 && fun(i + 19880100) )
printf("%d\n",i + 19880100);
return 0;
}
参考了tao的， 优化了下。。0ms,920k.
#include <stdio.h>
#include <string.h>
#include <math.h>
int dp[3000] = { 0 };
int p[2000];
int dx[50] = {0};
const int inf = sqrt ( 19891231);
int m[13] = {0,31,29,31,30,31,30,31,31,30,31,30,31};
void debug( )
{
#ifdef P
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
}
int fun(int year )
{
int temp, mon, day;
temp = year % 10000;
mon = temp / 100;
day = temp % 100;
if ( mon > 12 || mon <= 0 )
return 0;
else if ( day > m[mon] || day <= 0)
return 0;
else
return 1;
}
int main( )
{
debug( );
int i, j, n1, n2 = 0, k = 0;
n1 = sqrt(inf);
for ( i = 3; i <= n1; i += 2 ) {
if (dp[i / 2] )
continue;
for ( j = i * i; j <= inf; j += i + i)
dp[j / 2] = 1;
}
p[0] = 2;
k = 1;
for ( i = 1; i < (inf+1) / 2; i++)
if (!dp[i])
p[k++] = 2 * i + 1;
for ( i = 19880100; i <= 19891231; i++)
if (fun ( i ) )
{
for (j = 0; j < k; j++)
if ( i % p[j] == 0 )
break;
if ( j >= k )
dx[n2++] = i;
}
for ( i = 0 ; i < n2 ; i++)
printf("%d\n",dx[i]);
//printf("%d\n",n2);
return 0;
}
旭娃的。0ms. 988k
#include <stdio.h>
#include <math.h>
#include<stdlib.h>
char hash[100000], num[10000];
const int lim=(int ) sqrt( 19891250 );
int monday[13]= { 0, 1, -1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1 };
bool legal( int x )
{
int temp= x% 10000;
int mon= temp/ 100, day= temp% 100;
if( mon>=1&& mon<= 12 )
{
if( mon!= 2 )
{
if( day<= 30+ monday[mon] )
{
return true;
}
return false;
}
else
{
if( x< 19890000 )
{
if( day<= 30+ monday[mon]- 1 )
{
return true;
}
return false;
}
else
{
if( day<=30 + monday[mon] )
{
return true;
}
return false;
}
}
}
return false;
}
int main( )
{
for( int i= 2; i<= lim; ++i )
{
if( !num[i] )
{
for( int j= i+ i; j<= 1412; j+= i )
{
num[j]= 1;
} // Éž³ö 2- sqrt() Ö®ŒäµÄËØÊý
for( int j= 19880000/ i * i; j<= 19891231; j+= i )
{
if( j- 19880000> 0 )
{
hash[ j- 19800000 ]= 1;
}
} // œôœÓ×ÅÉž 19880000 - 19890000
}
}
for( int i= 80101; i<= 91231; ++i )
{
if( !hash[i]&& legal( i+ 19800000 ) )
{
printf( "%d\n", 19800000+ i );
}
}
system( "pause" );
return 0;
}