কোডটাতে লাস্ট টেস্ট কেসে TLE দেখানোর কারণ কী? 
#include<stdio.h>
int main()
{
int i, j, T, n, count;
scanf(“%d”, &T);
for(i = 1; i <= T; i++) {
count = 0;
scanf(“%d”, &n);
for(j = 1; j <= n; j++) {
if(n % j == 0) {
count++;
}
}
if(count == 2) {
printf(“%d is a prime number.\n”, n);
}
else {
printf(“%d is not a prime number.\n”, n);
}
}
return 0;
}
এভাবে করলে ভাই TLE ই হবে। ওখানে যেই কোডটা দেওয়া আছে তা হালকা চেঞ্জ করলেই হয়ে যাবে। এই টিউটোরিয়ালটার হেল্প নিতে পারো।
import static java.lang.Math.sqrt;
import java.util.Scanner;
/**
*
* @author Md Rifat
*/
public class SieveofEratosthenes {
public static int prime[]=new int[1000100];
static void isprime(){
for( int i = 2 ; i <=sqrt(1000000) ; i ++ ) {
if(prime[i]!=1){
for( int j = 2 ; i*j <= 1000000 ; j ++ ) {
prime[ i*j ] = 1;
}
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N;
N=sc.nextInt();
int num;
isprime();
for( int i = 0 ; i < N ; i ++ ) {
num=sc.nextInt();
if( prime[ num ] != 1 ) {
System.out.println(num+" is a prime number.");
}
else {
System.out.println(num+" is not a prime number.");
}
}
}
}
whats the problem in this code … CPU in last case
This method should run pretty fast.
#include <bits/stdc++.h>
#define optimize ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0) ;
#define ll long long
#define vi vector
#define pb push_back
#define lp(i,a,b) for(int i = a ; i <= b ; i ++)
#define rlp(i,a,b) for(int i = b ; i >= a ; i --)
#define a_sort(v) sort(v.begin(), v.end())
#define d_sort(v) sort(v.rbegin(), v.rend())
#define pii pair<int,int>
using namespace std ;
const int MOD = 1E9 + 7 ;
const int N = 1E6 ;
vector prime(N + 5, true);
void sieve() {
prime[0] = prime[1] = false ;
for(int i = 4 ; i <= N ; i += 2) prime[i] = false ;
for(int i = 3 ; ii <= N ; i += 2) {
if(prime[i]) {
for(int j = ii ; j <= N ; j += i) prime[j] = false ;
}
}
}
int main() {
#ifdef debug
freopen(“input.txt”, “r”, stdin) ;
freopen(“output.txt”, “w”, stdout) ;
#endif // debug
optimize
sieve() ;
int N ;
scanf("%d",&N) ;
int num ;
for( int i = 0 ; i < N ; i ++ ) {
scanf("%d",&num) ;
if( prime[ num ] ) {
printf("%d is a prime number.\n",num);
}
else {
printf("%d is not a prime number.\n",num);
}
}
}
public class SieveofEratosthenes {
public static boolean prime[]=new boolean[1000100];
static void isprime(){
for (int i = 0; i <=1000000; i++) {
prime[i]=true;
}
prime[0]=prime[1]=false;
int i = 2 ;
while(i*i <=1000000){
if(prime[i]==true){
for( int j = i*i ; j<=1000000; j=i+j ) {
prime[ j ] = false;
}
}
i++;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int reng=sc.nextInt();
int num;
isprime();
for( int i = 0 ; i <reng ; i ++ ) {
num=sc.nextInt();
if( prime[ num ] != false ) {
System.out.println(num+" is a prime number.");
}
else {
System.out.println(num+" is not a prime number.");
}
}
whats the problem 
First of all, in your isprime function, j must start with 2*i not i*i.
Secondly, I used the the same kind of algorithm in c++ and got AC. But previously you said you’re having TLE in the last case. This is probably because java is slower than c++ and there isn’t any extra time for java.
But still it can be solvable using Faster I/O.
Note: I’m not good at java and I haven’t tested it myself so I cannot guarantee that it will work but you can try.
What’s The Problem?
import java.util.Scanner;
public class SieveofEratosthenes {
public static boolean prime[] = new boolean[1000100];
static void isprime() {
for (int i = 3; i <= 1000000; i++) {
if(i%2==0){
prime[i] = true;
}else{
prime[i] = false;
}
}
prime[0] = prime[1] = prime[2] = false;
for (int j = 3; j * j <= 1000000; j += 2) {
if (prime[j] == false) {
for (int k = j * j; k <= 1000000; k += j + j) {
prime[k] = true;
}
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int reng = sc.nextInt();
int num;
isprime();
for (int i = 0; i < reng; i++) {
num = sc.nextInt();
if (prime[num] == false) {
System.out.println(num + " is a prime number.");
} else {
System.out.println(num + " is not a prime number.");
}
}
}
}
Done. Give it a try now.
//package AddHoc;
import java.util.Scanner;
public class BitwiseSieve {
public static int n = 1000090;
public static int prime[] = new int[1000100];
public static void isPrime() {
int x = (int) Math.sqrt(n);
prime[0] = 1;
prime[1] = 1;
for (int i = 4; i <= n; i += 2) {
prime[i] = 1;
}
for (int i = 3; i <= x; i += 2) {
if (prime[i] == 0) {
for (int j = i * i; j < n; j += i* 2) {
prime[j] = 1;
}
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int testCase = sc.nextInt();
isPrime();
for (int i = 0; i < testCase; i++) {
int num = sc.nextInt();
if (prime[num] != 0) {
System.out.println(num + " is not a prime number.");
} else {
System.out.println(num + " is a prime number.");
}
}
}
}
why i get CPU Limit Exceeded
@hjr265 I have used O(n*log(log(n))) solution.Why time TLE? Seive of Erathosthenes is the most efficient solution!
please check the submission!
I see you have solved the problem already.
As you may have realized already, you don’t need to do a full sieve for each case in the test. You can do a sieve once, and then lookup the same sieved array to answer for each case.
Yes… thanks for responding though 
@touhidurrr
include
using namespace std;
int main() {
unsigned long long n , a , c=0;
cin >> n ;
for(int i = 1 ; i <= n ; i++){
cin >> a ;
c = 0 ;
for(int x = a ; x > 1 ; x--){
if(a%x==0)
c++;
}
if(c > 1 )
cout << a << " " <<"is not a prime number."<<endl;
else if(c==1 )
cout << a <<" "<<"is a prime number."<<endl;
}
}
every time my answer is being accepted in the first 5 test cases … But on the 6 test case , it is showing wrong answer
i need help about the above description.
Sorry for bringing up this old conversation but, there’s a small issue on the problem statement. By going through the pseudocode of Shrabonti, one can tell that 1<=x<=10e6
But in the statement below,
It should be 10e6, not 106. This should be fixed to avoid confusion.
what’s the problem here in test case 2?
#include <stdio.h>
#include <string.h>
int main()
{
int N, i;
char n[1000100];
scanf("%d", &N);
for (i = 0; i < N; i++)
{
scanf("%d", &n[i]);
}
for (i = 0; i < N; i++)
{
if ((n[i] != 2 && n[i] != 3 && (n[i] == 1 || n[i] % 2 == 0 || n[i] % 3 == 0)))
{
printf("%d is not a prime number.\n", n[i]);
}
else
{
printf("%d is a prime number.\n", n[i]);
}
}
return 0;
}