SRM291Div2,250

この記事は約2分で読めます。

A prime number is an integer greater than 1 that has no positive divisors other than 1 and itself. The first prime numbers are 2, 3, 5, 7, 11, 13, 17, …

The number N is considered far from primes if there are no prime numbers between N-10 and N+10, inclusive, i.e., all numbers N-10, N-9, …, N-1, N, N+1, …, N+9, N+10 are not prime.

You are given an int A and an int B. Return the number of far from primes numbers between A and B, inclusive.

[java]
public class FarFromPrimes {

public int count(int A, int B) {
int[] prime = new int[B+11];//from 1 to B
prime[0]=0;//0 is not prime
prime[1]=0;
prime[2]=1;//2 is prime
prime[3]=1;
for (int i = 4; i < B+11; i++) {
prime[i]=1;
for (int j = 2; j <= i/2; j++) {
if(i%j==0){
prime[i]=0;
break;
}
}
}

int count=0;
for (int i = A; i <= B; i++) {
int frag=0;
for (int j = i-10; j <= i+10; j++) {
if (prime[j]==1) {
frag=1;
break;
}
}
if (frag==0) {
count++;
}
}
return count;
}

}
[/java]

コメント

タイトルとURLをコピーしました