N-th Prime


This is a companion discussion topic for the original entry at https://toph.co/p/n-th-prime

why this is given:

sympy is an external module and thus is not supported by Toph.
You can use standard library functions and standard modules only.
It is the same for any other online judges.

1 Like

I am getting RE in the 3rd case can someone please tell me what might be the reason?

Thanks

@hjr265 my Python 3 code is not being accepted. Runtime for python should be increased 3x.

1 Like

Thanks, my Python3 submission has been accepted.

1 Like

@hjr265
I think the runtime for Python should be 5x
I have optimized my python code very much but even then it took nearly 3s to run it. Then if a noob coder try to implement sieve here, how can he/she do it?
Thus the runtime should be 5x.

@touhidur
i’m getting WA on test 3.can u help?

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
int main(){
ll n;cin>>n;vector ans;
vector ls(500000,1);ls[1]=0;
for(int i=1;ii<=500000;++i){
if(ls[i]!=0){
for(int u=2;i
u<500000;u++) ls[i*u]=0;
}}
for(int i=1;i<500000;++i){
if(ls[i]==1) ans.push_back(i);}
cout<<ans[n-1];
return 0;
}

@EmONIIT11
Initializing vector like this often fails (for me).
Try memset instead.

1 Like

here is my code i got WA in 3rd case what’s the problem can anyone explain???
#include<stdio.h>
int main()
{
long long n,i,count=0,flag;
while(scanf("%lld",&n)!=EOF){
flag=0;
for(i=1;i<=5000000;i++){
flag=0;
if(i==2||i==3||i==5||i==7||i==11||i==13)flag=0;
else if(i%2==0||i%3==0||i%4==0||i%5==0||i%6==0||i%7==0||i%8==0||i%9==0||i%11==0||i%13==0||i==1||i==0)
{
flag=1;
}

    if(flag==0)
    {
            count++;
            }
    if(count==n)
    {
            printf("%lld\n",i);
        break;
    }
        }
    count=0;}
return 0;

}

My solution takes 0.6s with the sieve of Erathostenes in Python. You’re probably missing something.

Use that for this problem first.

#include<stdio.h>
int prime_nth(int n)
{
int a,i,co=0,b=0;

for(i=2; i>0; i++)
{
    b=0;
    for(a=2; a<i; a++)
    {
        if(i%a==0)
        {
            b=1;
            break;
        }

    }
    if(b==0)
    {
        co++;
    }
    if(co==n)
    {
        printf("%d",i);
        return 0;
    }}}

int main()
{int n;
scanf("%d",&n);
prime_nth(n);

    return 0;

}
…What is the problem with this program…I got wrong answer in 3rd case…plz solve this.

please help me 3rd case worng…

def nth_prime_number(n):
prime_list = [2]
num = 3
while len(prime_list) < n:
for p in prime_list:
if num % p == 0:
break
else:
prime_list.append(num)
num += 2
return prime_list[-1]

n = int(input())
print(nth_prime_number(n))

it is also my problem…if anyone can…please help me.

My code works to print nth prime but it seems memory limit exceeded :frowning:

n = int(input())
r = (n+1)**2
nth = n - 1
d = [x for x in range(2, r)]
non_prime = []
for i in range(2, r):
for x in d:
if i % x == 0 and x != 1 and x != i:
non_prime.append(i)

non_prime = list(set(non_prime))
prime_numbers = [x for x in d if x not in non_prime]
print(prime_numbers[nth])