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

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

Time limit exceeds
Послано Atul Shanbhag 13 апр 2015 22:16
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MAX 100000000

void prime(int n)
{
    int i,j,temp,count=0;

    for(i=2;i<=MAX;i++)
    {
        temp=0;
        for(j=2;j<=sqrt(i);j++)
        {
            if(i%j==0)
            {
                temp=1;
                break;
            }
        }
        if(temp==0)
        {
            count++;
        }
        if(count==n)
        {
            printf("%d\n",i);
            break;
        }
    }
}

int main()
{
   int n,i;

   scanf("%d",&n);
   int arr[n];

   for(i=0;i<n;i++)
   {
       scanf("%d",&arr[i]);
   }
   for(i=0;i<n;i++)
   {
       prime(arr[i]);
   }

   return 0;
}

this is my code...its working perfectly fine on codeblocks...ive used two more methods 1. where in the function ive run the loop till i/2 not sqrt(i) which is also correct but i presume will take more loops and therefor less efficient code. 2. i use pointer in main functon to avoid using arrays (not sure it makes difference but still) and offcourse this code up...none of them are working below time limit even though they give correct output...any suggestions?
Re: Time limit exceeds
Послано Md. Shahedul Islam (Shahed) 7 июн 2015 13:25
the segment you wrote to identify if a number is prime or not is much time killing,
rather you may use this function like this:
----------------------------------------------------------------------------
bool is_prime(int n)
{
    if(n < 2) return 0;
    else if(n == 2) return 1;
    else if(n%2 == 0) return 0;

    int root = sqrt(n);

    for(int i = 3; i <= root; i += 2) {
        if(n % i == 0) return 0;
    }

    return 1;
}
----------------------------------------------------------------------------
Hints: 2 is the only even number which is prime.

then you may store prime numbers in an array.
finally the program seems to be like this... :
---------------------------------------------------------------------------
#include <iostream>
#include <cmath>
using namespace std;

bool is_prime(int n)
{
    //if(n < 2) return 0;
    //else if(n == 2) return 1;
    //else if(n%2 == 0) return 0;    // this lines aren't necessary for this program.

    int root = sqrt(n);

    for(int i = 3; i <= root; i += 2) {
        if(n % i == 0) return 0;
    }

    return 1;
}

int main()
{
    int k, i, n, *num, prime_num[15001] = {0, 2};    // 2 is in 1st position.

    for(n = 3, i = 2; i <= 15000; n += 2)
        if(is_prime(n)) prime_num[i++] = n;

    cin >> k;

    num = new int [k];

    for(i = 0; i < k; i++) cin >> num[i];

    for(i = 0; i < k; i++)
        cout << prime_num[num[i]] << '\n';

    delete [] num;

    return 0;
}
---------------------------------------------------------------------------------