[UVa] 10200 - Prime Time

題目網址: http://goo.gl/0DBxKc

題意:
(from luckycat)


解法: 建質數表檢查。

TAG: Prime

注意: 輸出的時候最好加上machine epsilon

程式碼:

	/**
	* Tittle: 10200 - Prime Time
	* Author: Cheng-Shih, Wong
	* Date: 2015/05/12
	*/
	// include files
	#include <iostream>
	#include <cstdio>
	#include <cstring>
	#include <vector>
	using namespace std;
	// definitions
	#define FOR(i,a,b) for( int i=(a),_n=(b); i<=_n; ++i )
	#define clr(x,v) memset( x, v, sizeof(x) )
	#define N 10005
	#define MAX_PRIME 10000
	typedef vector<int> VI;
	// declarations
	int a, b;
	bool isprime[N];
	VI prime;
	int pre[N];
	// functions
	void init( void )
	{
	clr( isprime, true );
	prime.clear();
	isprime[0] = isprime[1] = false;
	FOR( i, 2, MAX_PRIME ) if( isprime[i] ) {
	prime.push_back( i );
	for( int j=i*i; j <= MAX_PRIME; j+=i )
	isprime[j] = false;
	}
	clr( pre, 0 );
	VI::iterator it;
	int v;
	bool p;
	FOR( i, 0, MAX_PRIME ) {
	v = i*i+i+41;
	p = true;
	for( it=prime.begin(); it!=prime.end(); ++it ) {
	if( (*it)*(*it) > v ) break;
	if( v%(*it) == 0 ) {
	p = false;
	break;
	}
	}
	if( p )
	++pre[i];
	}
	/*
	FOR( i, 0, 45 ) {
	printf( "%d^2+%d+41 = %d, pre[%d] = %d\n", i, i, i*i+i+41, i, pre[i] );
	}
	*/
	FOR( i, 1, MAX_PRIME )
	pre[i] += pre[i-1];
	}
	// main function
	int main( void )
	{
	int val;
	init();
	// input
	while( scanf( "%d%d", &a, &b )==2 ) {
	// output
	if( a == 0 ) val = pre[b];
	else val = pre[b]-pre[a-1];
	printf( "%.2lf\n", val*100.0/(b-a+1) + 1e-6 );
	}
	return 0;
	}

view raw 10200 - Prime Time.cpp hosted with ❤ by GitHub