ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

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

why I always got WA on test #2?
Послано ss 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
Re: why I always got WA on test #2?
Послано v0id 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
Re: why I always got WA on test #2?
Послано Romko [Lviv NU] 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?
Послано Глащенко Никита 15 сен 2008 21:59
I set 190000.some problem.
Re: why I always got WA on test #2?
Послано maruf10 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;
}
Re: why I always got WA on test #2?
Послано ahmedov(NUUz_2) 1 мар 2009 18:39
Use __in64 instead of long!
Re: why I always got WA on test #2?
Послано Shahin Mohammed Faroqe 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]
Re: why I always got WA on test #2?
Послано Shahin Mohammed Faroqe 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