Hatena::Grouptopcoder

練習帳

 TopCoder(delta2323) / Codeforces(delta) / twitter

2011-09-11

[][] Codeforces Beta Round #86 Div. 2 E. Double Happiness 12:28 はてなブックマーク -  Codeforces Beta Round #86 Div. 2 E. Double Happiness - 練習帳

問題文

 問題文


分析

 3以上の素数が2つの平方数の和で書けるための必要十分条件は4で割った余りが1である事です.*1

従って,そのような素数と(範囲内にあるならば,)2を数え上げる事になります.

 エラトステネスのふるいを用いるとTLEを起こしてしまうので,奇素数だけを求めるふるいを用いています.下のコードのprimes[i]には,iが1以外の奇数なら素数かの情報を正しく格納していますが,偶数についてはその保証はありません.

 自分自身この方法は始めて知りました.

修正コード

 mengcowさんのコードを写経した後,自分で書いてみました.

#include <iostream>
#include <bitset>

using namespace std;

const int mx = 300000001;
   bitset<mx> primes;

int main(){
  int l,r;
  while(cin >> l >> r){
     primes.set();
    for(int i = 3; i*i <= r; i+=2){
      if(primes[i]){
	for(int j = i*i; j <= r; j += i*2){
	  primes[j] = false;
	}
      }
    }
    
    int ret = (l <= 2 && 2 <= r) ? 1 : 0;

    for(int now = 5; now <= r; now += 4){
      if(now >= l && primes[now]){
	ret++;
      }
    }
    cout << ret << endl;
  }
  return 0;
}

余談

 これだとTLEとなりました.上のコードでグローバル変数のbitsetをローカル変数に移動させただけです.

#include <iostream>
#include <bitset>

using namespace std;

const int mx = 300000001;

int main(){
  int l,r;
  while(cin >> l >> r){
    primes.set();
    bitset<mx> primes;

    for(int i = 3; i*i <= r; i+=2)
      if(primes[i])
	for(int j = i*i; j <= r; j += i<<1)
	  primes[j] = false;
    
    int ret = (l <= 2 && 2 <= r) ? 1 : 0;

    for(int now = 5; now <= r; now += 4){
      if(now >= l && primes[now]){
	ret++;
      }
    }
    cout << ret << endl;
  }
  return 0;
}