Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

813ms。。。晕,在苯地秒出啊

Posted by KatrineYang at 2017-01-23 05:15:45 on Problem 3006
#include <iostream>
#include <stdio.h>
using namespace std;

bool isPrime[1000000] = {false};
int primeList[100000];
int gs = 0;

void getPrime(){
	isPrime[2] = 1;
	for(int sqt = 1; sqt < 1000; sqt++){
		int start = (sqt%2==0) ? sqt*sqt+1 : sqt*sqt+2;
		int end = (sqt+1)*(sqt+1);
		for(int n = start; n < end; n += 2){
			bool isP = true;
			for(int i = 0; i < gs; i++){
				if(primeList[i] > sqt) break;
				if(n%primeList[i] == 0){
					isP = false;
					break;
				}
			}
			if(isP){
				primeList[gs] = n;
				gs++;
				isPrime[n] = true;
			}
		}
	}
}

int main() {
	getPrime();
	//cout << 1 << endl;
	int a,d,n;
	while(1){
		scanf("%d%d%d", &a,&d,&n);
		if(!a && !d && !n) break;
		int cnt = 0;
		for(int i = 0; ; i++){
			if(isPrime[a+i*d]) cnt++;
			if(cnt == n){
				printf("%d\n", a+i*d);
				break;
			}
		}
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator