Обсуждение @ 1086. Криптография @ Timus Online Judge

ss why I always got WA on test #2? [7] // Задача 1086. Криптография 22 июл 2004 14:58

I 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

v0id Re: why I always got WA on test #2? [6] // Задача 1086. Криптография 26 мар 2007 23:44

i have the same problem in c++.
i tested on
http://ru.wikipedia.org/wiki/%D0%A1%D0%BF%D0%B8%D1%81%D0%BE%D0%BA_%D0%BF%D1%80%D0%BE%D1%81%D1%82%D1%8B%D1%85_%D1%87%D0%B8%D1%81%D0%B5%D0%BB
i used Eratosphene's algorythm

Edited by author 26.03.2007 23:46

Romko [Lviv NU] Re: why I always got WA on test #2? [5] // Задача 1086. Криптография 20 май 2007 02:40

Maybe you generate only small numbers, try to use array size 170001, and you'll get AC!

Глащенко Никита Re: why I always got WA on test #2? [4] // Задача 1086. Криптография 15 сен 2008 21:59

I set 190000.some problem.

maruf10 Re: why I always got WA on test #2? [3] // Задача 1086. Криптография 17 сен 2008 00:09

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;
}

ahmedov(NUUz_2) Re: why I always got WA on test #2? [2] // Задача 1086. Криптография 1 мар 2009 18:39

Use __in64 instead of long!

Shahin Mohammed Faroqe Re: why I always got WA on test #2? [1] // Задача 1086. Криптография 30 окт 2010 03:42

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]

Shahin Mohammed Faroqe Re: why I always got WA on test #2? // Задача 1086. Криптография 30 окт 2010 03:43

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

Обсуждение задачи 1086. Криптография