Time: 0.001
Algorithm: Sieve

Edited by author 26.05.2024 06:13

#include "bits/stdc++.h"

#define int long long
using namespace std;

vector<int> eratosfen() {
    int n = 168841;
    vector<bool> res(n + 1, false);
    for (int i = 2; i <= n; ++i) {
        if (!res[i]) {
            for (int j = i * i; j < n; j += i) {
                res[j] = true;
            }
        }
    }
    vector<int> res2;
    for (int i = 2; i < res.size(); ++i) {
        if (!res[i]) {
            res2.push_back(i);
        }
    }
    return res2;
}

signed main() {
    int t;
    cin >> t;
    vector<int> a = eratosfen();
    while (t--) {
        int n;
        cin >> n;
        if (n == 1) {
            cout << 2;
            continue;
        }
        cout << a[n - 1] << endl;
    }
}

It's written that the numbers don't exceed 15000, but it's most likely that the test 2 contains number 15001, cuz i was receiving WA until i changed border to 163847 (is 15001st prime number)

#include<stdio.h>
int main(){



int testCase,i,j,l;

scanf("%d",&testCase);

for(l=0;l<testCase;l++){
  int k=0,count;
  scanf("%d",&count);
int pnumber=0;

for(j=2;k<count;j++){

int flag=0;
for(i=2;i*i<=j;i++){
    if(j%i==0){
        flag=1;
        break;
    }
}

if(flag){

}else{
    pnumber=j;
    k++;
}

}
printf("%d",pnumber);

}

return 0;

}

import math
m = int(input())
mass = [int(input()) for i in range(m)]
def bit_sieve(n):
    if n < 2:
        return []
    bits = [1] * n
    sqrt_n = int(math.sqrt(n)) + 1
    for i in range(2, sqrt_n):
        if bits[i - 2]:
            for j in range(i + i, n + 1, i):
                bits[j - 2] = 0
    return bits
for j in range(m):
    k = mass[j]
    sieve = bit_sieve(int(1.5 * k * math.log(k)) + 1)
    i = 0
    while k:
        k -= sieve[i]
        i += 1
    print(i + 1)

o_o

Edited by author 10.11.2020 12:55

Hi everyone!

If you are getting TLE in Test #2 or maybe another, I would like to give you a little help:

-> Test #2 seems to give large numbers (like 15000), and it gives you those numbers in increasing order. Think about it.

Now, if that isn't enogh, I can give you a little more help:

-> Create an array / vector / list which will store the prime numbers you find.

-> Create an algorithm that determines whether a number is prime or not (remember to only       compare with odd numbers smaller than the square root of the number from which you are trying to figure out its primality).

-> Create a function that calculates the n-th prime number. For that create a counter which increases everytime you find a new prime number and store that prime number in your array / vector / list.

-> Finally, remember the thing I said at the beginning of this post! :D

Hope it helps. :D

#include<bits/stdc++.h>
using namespace std;
int primes[300001],nprime;
int mark[1000002];
#define MAX_SIZE 1000005

void sieve(){
int i,j,limit = sqrt(MAX_SIZE*1.0)+2;
mark[1]=1;
for(i=4;i<=MAX_SIZE;i+=2)mark[i]=1;
primes[nprime++]=2;
for(i=3;i<=MAX_SIZE;i+=2){
    if(!mark[i]){
        primes[nprime++]=i;
        if(i<=limit){
            for(j=i*i;j<=MAX_SIZE;j+=i*2){
                mark[j]=1;
            }
        }
    }
}
}

int main(){
sieve();
int n;
cin>>n;
while(n--){
    int x;
    cin>>x;
    cout<<primes[x-1]<<endl;
}

}

#include <bits/stdc++.h>
using namespace std;
#define MAX_SIZE 1000005
void SieveOfEratosthenes(vector<int> &primes)
{
    bool IsPrime[MAX_SIZE];
    memset(IsPrime, true, sizeof(IsPrime));
    for (int p = 2; p * p < MAX_SIZE; p++)
    {
        if (IsPrime[p] == true)
        {
            for (int i = p * p; i < MAX_SIZE; i += p)
                IsPrime[i] = false;
        }
    }
    for (int p = 2; p < MAX_SIZE; p++)
    if (IsPrime[p])
            primes.push_back(p);
}

int main()
{
    int t;
    cin>>t;
    vector<int> primes;
    SieveOfEratosthenes(primes);
    while(t--){
        int n;
    cin>>n;
    cout<<primes[n-1]<<endl;
    }
    return 0;
}

#include <iostream>
#include <vector>
#include <iterator>
using namespace std;
int n = 163841;
vector<char> prime(n + 1, true);
void eratosphen() {
    prime[0] = false;
    prime[1] = false;
    for (int i1 = 2; i1 <= n; ++i1)
        if (prime[i1])
            if (i1 * 1ll * i1 <= n)
                for (int j1 = i1 * i1; j1 <= n; j1 += i1)
                    prime[j1] = false;
}
int main() {
    eratosphen();
    vector <long long> list(15001); int i = 2;
    for (int il = 1; il <= 15000;) {
        for (int ip = 2; ip < prime.size(); ip++) {
            if (prime[ip]) {
                list[il] = ip;
                il++;
            }
        }
    }
    int k;
    cin >> k;
    for (int i0 = 0; i0 < k; i0++){
        int m;
        cin >> m;
        cout << list[m] << '\n'; \
    }
}

#include <iostream>

using namespace std;

int prime[15001];
bool num[163848];
void sieve() {
    num[2]=true;
    prime[1]=2;
    long int i,j,k;
    for(i=3;i<163848;i+=2) num[i]=1;
    for(i=2,j=3;i<=15000;j+=2) {
        if(num[j]) {
            for(k=j;k*j<=163848;k+=2) num[k*j]=0;
            prime[i]=j;
            i++;
        }
    }
}

int main() {
    sieve();
    int t;
    cin>>t;
    while(t--) {
        int m;
        cin>>m;
        cout<<prime[m]<<endl;
    }
}


Why am I getting RTE in test #1?

Edited by author 13.09.2019 08:33

What is the problem with my code?

#include <iostream>
using namespace std;
#include <cmath>

bool check_prime(double n) {
    int c;
    for (c=2;c<= sqrt(n);c++) {
        if((int) n%c==0)
            return 0;
    }
    if(c==(int) n)
        return 1;
}

int nth_prime(int n){
    int m=1;
    while (n>0) {
        m++;
        if (m == 2) {
            n--;
        }
        if (m%2!=0) {
            if (check_prime(m)==1) {
                n--;
            }
        }
    }
    return m;

}

int main()
{
    int n,m,i,a[15000],s;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    for(i=0;i<n;i++){
        s = nth_prime(a[i]);
        printf("%d\n",s);
    }
    return 0;
}

#include <iostream>
#include <math.h>
using namespace std;

int Prime[15000], nPrime;
int mark[15000];

void sieve(int n)
{
    int i, j, limit=sqrt(15000)+2;

    mark[1]=1;  ///mark is not prime...so...

    for(i=4; i<=n; i+=2)
        mark[i]=1;

    Prime[nPrime++]=2;

    for(i=3; i<=n; i+=2)
        if(!mark[i])
        {
            Prime[nPrime++]=i;
            if(i<=limit)
            {
                for(j=i*i; j<=n; j+=i*2)
                    mark[j]=1;
            }
        }
}

int main()
{
    sieve(15000);
    int n;
    cin >> n;
    int arr[2000];
    //cout << Prime[n-1] << endl;

    for(int i=0; i<n; i++)
        {
            cin >> arr[i];
        }
    for(int i=0; i<n; i++)
        cout << Prime[arr[i]-1] << endl;

        return 0;
}

It looks like a very simple problem. In pure C, but not in Python! :)
'Time limit exceeded' despite using precomputed tuple of primes (first 100 and each 100th or 50th), Eratosthenes' sieve, optimizations, wheel factorization etc.
Time is 2.10-2.30 regardless of method !!! WTF???
On my PC it finds a prime very fast:

-----
Enter the number... 14999
14999-th prime number is 163819
Elapsed time is 0.0010540485382080078
-----

On my computer and python implementation (Intel i3, Linux Fedora 27/ CPython 3.6.4) average time per prime is about 1 ms o less.

How to solve the problem in this strangely slow Python implementation?

Edited by author 10.03.2018 05:38

#include<bits/stdc++.h>
using namespace std;
int arr[15000],newarr[15000];
void sieve()
{
    arr[0]=1;
    arr[1]=1;
    newarr[1]=2;
    for(int i=4; i<15000; i+=2)
        arr[i]=1;
    for(int i=3; i<15000; i+=2){
        if(arr[i]!=1){
            for(int j=i*2; j<15000; j+=i){
                arr[j]=1;
            }
        }
    }
}

int main()
{
    int n, t, k=1;
    sieve();
    //cin>>n;
    for(int i=1; i<15000; i++){
        if(arr[i]!=1){
            newarr[k]=i;
            k++;
        }
    }
    cin>>t;
    while(t--){
        cin>>n;
        cout<<newarr[n]<<endl;
    }

    return 0;
}

#include<iostream>

using namespace std;

bool isPrime(int a)
{
    int i;
    if(a==1) return 0;
    for(i=2; i<a; i++){
        if(a==2) return 1;
        else{
            if(a%i==0) return 0;
        }
    }
    return 1;
}

int main()
{
    int t,j,b,count=0;
    cin>>t;
    while(t--){
        int k=1;
        cin>>j;
        while(count!=j){
            b= isPrime(k);
            if(b==1) count++;
            k++;
        }

        cout<<--k<<endl;
        count=0;
    }

    return 0;
}

I am new in coding..please help me to solve this problem

import math
def getList(maxNumber):
    primeLst = []
    for num in range(2,15000):
        if all(num%i!=0 for i in range(2,int(math.sqrt(num))+1)):
           primeLst.append(num)
           if len(primeLst)==maxNumber:
                return primeLst

lst = []
for x in range(int(input())):
    lst.append(int(input()))
primeNumbers = getList(max(lst))
for x in lst:
    print(primeNumbers[x-1])

I don't know why my code is error in testcase 2
Can anybody help me out of here ?

I have used sieve theorem but i am still getting TLE! i need my code optimization .here is my code:

#include<iostream>
#include<cmath>
using namespace std;
#define TOTAL 163841
int main()
{

 int ara[TOTAL];

    for(int i=2; i<TOTAL; i++)
    {
        ara[i]=1;

    }
     int root = sqrt(TOTAL);

    for(int i=2; i<=root;i++)
    {
        for(int j=2; i*j<=TOTAL; j++) \\ Using  sieve theorem
        {
            ara[i*j]=0;
        }
    }
int T;
 int n;
cin >> T;
int r,k;
for(int l=1; l<=T; l++)
{

cin >> n;

if(n<=15000)
{
int ara2[n];
for(k=2,r=1;r<=n;k++)
{
    if(ara[k]==1)
    {
        ara2[r]=k; \\ copying the prime numbers to the ara2[]
        r++;
    }

}

cout << ara2[n] << "\n"; // cout the last num of ara2[]

}
}
return 0;
}

Edited by author 13.08.2017 12:49