|
|
back to boardShow all messages Hide all messagesI just find all 15000 prime numbers
and put them in an array
then writeln(a[n]) for each n
isn't it correct?
I just cannot understand Maybe you generate only small numbers, try to use array size 170001, and you'll get AC! I set 190000.some problem. where is the problem???this code fails in test#2 :(
#include<stdio.h>
#define size 150001
long a[size];
long p[size];
int main()
{
long i,j,k,m=0,n,t;
a[0]=1;
a[1]=1;
for(i=4;i<=size;i+=2)
a[i]=1;
for(i=3;i<=size;i+=2)
{
if(a[i]==0)
{
k=size/i;
for(j=i;j<=k;j++)
a[j*i]=1;
}
}
for(i=0;i<=size;i++){
if(a[i]==0)
p[m++]=i;
}
scanf("%ld",&t);
while(t--){
scanf("%ld",&n);
printf("%ld\n",p[n-1]);
}
return 0;
} Use __in64 instead of long! you user java language for this problem
first generate prime number and put it into a array prime[15000]
and the scan the number ex. 10
and print prime[10] There is my i got AC
import java.util.*;
public class Main
{
public static long prm[] = new long[15001];
public static void main( String args[] )
{
Main obj = new Main();
obj.sieve(163841);
Scanner in = new Scanner(System.in);
int t=in.nextInt();
while(t>0)
{
t--;
int n=in.nextInt();
System.out.println(prm[n]);
}
}
public void sieve (int outerBounds) {
long start = System.currentTimeMillis();
int N = outerBounds;
boolean[] isPrime = new boolean[N + 1];
for (int i = 2; i <= N; i++) {
isPrime[i] = true;
}
for (int i = 2; i*i <= N; i++) {
if (isPrime[i]) {
for (int j = i; i*j <= N; j++) {
isPrime[i*j] = false;
}
}
}
int j=1;
for (int i = 2; i <= N; i++) {
if (isPrime[i])
{
prm[j]=i;
j++;
}
}
}
}
here i user sieve method
Edited by author 30.10.2010 03:44
Edited by author 30.10.2010 03:45 |
|
|
