I am getting WA in my solution. I used sieve of eratosthenes. Please help me figure out the problem Link to my solution
I think there’s something wrong in your implementation of the Sieve of Eratosthenes. Here’s my solution in C++. Hope it helps you figure out what’s wrong.
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
int preComp[(int) 1e6 + 1] = {0};
void sieve(int n){
bool prime[n+1];
memset(prime,true,sizeof(prime));
for(int p=2;p*p<=n;p++){
if(prime[p] == true){
for(int i=p*p;i<=n;i+=p)
prime[i] = false;
}
}
int c = 5;
preComp[c] = 1;
for(int i=c+1;i<=n;i++){
if(prime[i] && prime[i-2]){
preComp[i] = preComp[i-1] + 1;
}
else{
preComp[i] = preComp[i-1];
}
}
}
int main() {
sieve(1e6);
int t;
cin >> t;
while(t>0){
int n;
cin >> n;
cout<<preComp[n];
cout<<endl;
t--;
}
return 0;
}
3 Likes
@dexterity, here’s your ACfied code.
import java.util.*;
import java.lang.*;
import java.io.*;
public class Main {
static class FastReader {
BufferedReader br;
StringTokenizer st;
public FastReader() {
br = new BufferedReader(new InputStreamReader(System.in));
}
String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong() {
return Long.parseLong(next());
}
double nextDouble() {
return Double.parseDouble(next());
}
String nextLine() {
String str = "";
try {
str = br.readLine();
} catch (IOException e) {
e.printStackTrace();
}
return str;
}
}
static int gcd(int a, int b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
static class mysort implements Comparable<mysort>
{
int height;
int width;
int index;
mysort(int height,int width,int index){
this.height=height;
this.width=width;
this.index=index;
}
public int compareTo(mysort ms){
if(this.height>ms.height){
return 1;
}
else if(this.height<ms.height){
return -1;
}
else{
return this.width-ms.width;
}
}
}
static class mysort2 implements Comparable<mysort2>
{
int index;
int ans;
mysort2(int index,int ans){
this.index=index;
this.ans=ans;
}
public int compareTo(mysort2 ms){
return this.index-ms.index;
}
}
static int lower(int start,int end,int arr[],int n,int x){
int mid=(start+end)/2;
if(start>end){
return -1;
}
if(arr[mid]==x && (mid-1)>=0 && arr[mid-1]<x){
return mid;
}
else if(arr[mid]>=x && (mid-1)>=0){
return lower(start,mid-1,arr,n,x);
}
else if(arr[mid]<x &&(mid+1)<n){
return lower(mid+1,end,arr,n,x);
}
else if(arr[mid]==x && (mid==0)){
return mid;
}
return -1;
}
static int upper(int start,int end,int arr[],int n,int x){
int mid=(start+end)/2;
if(start>end){
return -1;
}
if(arr[mid]==x && (mid+1)<n && arr[mid+1]>x){
return mid;
}
else if(arr[mid]>x && (mid-1)>=0){
return upper(start,mid-1,arr,n,x);
}
else if(arr[mid]<=x &&(mid+1)<n){
return upper(mid+1,end,arr,n,x);
}
else if(arr[mid]==x && (mid==(n-1))){
return mid;
}
return -1;
}
// method to return LCM of two numbers
static int lcm(int a, int b)
{
return (a / gcd(a, b)) * b;
}
static void calculate(int arr[],int n,int x){
for(int i=x*x;i<=n;i=i+x){
if(i<0){
break;
}
arr[i]=1;
}
}
public static void main(String args[]) throws Exception
{
// try {
// FileOutputStream output=new FileOutputStream("C:\\Users\\vishr\\OneDrive\\Desktop\\java\\output.txt");
// PrintStream out=new PrintStream(output);
// //Diverting the output stream into file "temp.out".Comment the below line to use console
// System.setOut(out);
// InputStream input=new FileInputStream("C:\\Users\\vishr\\OneDrive\\Desktop\\java\\input.txt");
// //Diverting the input stream into file "temp.in".Comment the below line to use console
// System.setIn(input);
// } catch (FileNotFoundException e) {
// e.printStackTrace();
// }
FastReader sc = new FastReader();
int n = 1000002;
boolean isPrime[] = new boolean[n];
for(int i=0;i<n;i++)
isPrime[i] = false;
for(int i=3;i<n;i+=2)
isPrime[i] = true;
for(int i=3;i*i<n;i+=2)
if(isPrime[i])
for(int j=i*i;j<n;j+=i)
isPrime[j] = false;
isPrime[2] = true;
int store[]=new int[n+1];
store[0] = 0;
store[1] = 0;
for(int i=2;i<n;i++){
if(isPrime[i] && isPrime[i-2]){
store[i]=store[i-1]+1;
}
else{
store[i]=store[i-1];
}
}
int test=sc.nextInt();
for(int t=0;t<test;t++){
int q=sc.nextInt();
System.out.println(store[q]);
}
}
}
//1 2 3 2 1
1 Like