10200 - Prime Time

Joseph Kurniawan · Post by **Joseph Kurniawan** » Fri Sep 05, 2003 9:49 am

I suggest to use "semi-hardcode".

for(i=0;i<=10000;i++){
  result=i*i+i+41;
  if(result%2!=0){
    j=sqrt(result);
    for(k=3;k<=j;k+=2){
      if(result%k==0) break;
      }
    if(k>j) primality[i]=1;
    }
  }

So, in the main function you just check from the range a to b, how many times primality=1 occurs and just count the percentage!!
Hope it helps!!

Riyad · Post by **Riyad** » Fri Sep 05, 2003 8:55 pm

thanx buddy got it ac after so many submissions . u r semi hard core algo worked out perfectly well.
Bye
Riyad

mohiul alam prince · Post by **mohiul alam prince** » Mon Nov 10, 2003 10:05 am

riyad
i think ur algo is not good for prime time

1. u collect ur prime by samims algo
2. then u will store the equations value is prime or not(it will be stored in the another array(MMM[]))
3.then u take input and chake is this input is prime or not then count

prince
10-11-2003

kamrul · Post by **kamrul** » Mon Dec 29, 2003 9:45 am

I m getting TLE for This Problem
Can anyone tell me what is the problem with my algo.

It runs well for the worst inputs

as:
0 10000
[cpp]
Code Removed
[/cpp]

Thanks.

sohel · Post by **sohel** » Mon Dec 29, 2003 1:58 pm

Hi Kamrul,
Your algorithm is correct in terms of accuracy but not for the time limit.
From your code, it looks like you are checking for prime for every number in the range. Why don't you first process all the numbers before the loop and store it in an array. And for every case just check for validity from the array.

hope it helps.

kamrul · Post by **kamrul** » Wed Dec 31, 2003 11:27 am

Now I got AC

Thank you Sohel.
Your trick helped me.

nford85 · Post by **nford85** » Tue Aug 31, 2004 4:54 am

Hi

This seems to be an unusual request for this particular problem - from a preliminary search i did most people seemed to have problems with getting into the time limit. I can get into the time limit but somehow I just get WA every time. Can someone supply me with some sample inputs and outputs so I can try and find the problem myself?

Thanks
Nick

Minilek · Post by **Minilek** » Tue Aug 31, 2004 6:55 am

good luck

Input:

Code: Select all

Output:

Code: Select all

nford85 · Post by **nford85** » Tue Aug 31, 2004 2:36 pm

Thanks thats a great help

branka · Post by **branka** » Tue Nov 16, 2004 9:50 pm

HALO!!!
What does mean: "You must read until the end of the file." ??

All other problems had something like Problem number 694: " A line that contains two negative integers follows the last case."

Is it posible, that i get TLE because it doesn't read the last line??

Here is my code in Java:

Code: Select all

/* @JUDGE_ID: 50020MM 10200 java */
import java.io.*;
import java.util.*;
import java.text.DecimalFormat;
import java.lang.Object;


class Main{
	static String ReadLn (int maxLg)
	{
	 byte lin[] = new byte [maxLg];
	    int lg = 0, car = -1;
	    String line = "";
	    try
	    {
	        while (lg < maxLg)
	        {
	            car = System.in.read();
	            if ((car < 0) || (car == '\n')) break;
	            lin [lg++] += car;
	        }
	    }
	    catch (IOException e)
	    {
	        return (null);
	    }
	    if ((car < 0) && (lg == 0)) return (null);
	    return (new String (lin, 0, lg));
    }



	public static void main(String[] args)
	{
		Main myWork = new Main();
        myWork.Begin();
	}
	void Begin(){
		  java.text.DecimalFormat dec = new java.text.DecimalFormat(",##0.00");
          String input;
          StringTokenizer idata;
          int a, b, stevec, k, rezultat, rez;
          double j, procent, st;

          while((input = Main.ReadLn (255)) != null)
          {
				idata = new StringTokenizer (input);

				a = Integer.parseInt(idata.nextToken());
				b = Integer.parseInt(idata.nextToken());
				stevec = 0;

				if((a>b)||(a>10001)||(b>10001)){
					break;
				}//if
				rezultat = a*a + a + 41;
				if(b<40){
				 	System.out.println("100.00");
				}
				else{
					for(int i=a;i<=b;i++){
						if((rezultat%2!=0)||(rezultat%3!=0)){
							j=Math.sqrt(rezultat);
							for(k=5;k<=j;k+=2){
								if(rezultat%k==0){
									break;
								}//if
							}//for
							if(k>j){
								stevec++;
							}//if
						}//if
						rezultat = rezultat+2*i+2;
  					}//for
					st = b - a + 1;
					procent = (Math.round(((stevec*100)/st)*100))/100.0;
					String str = dec.format(procent).toString();
					System.out.println(str.replace(',', '.'));
				}//else
		}//while
	}//Begin
}//Main
/*@END_OF_SOURCE_CODE*/

Or is it something wrong with my algoritem???

Pleas help me, I am really loosing my head on this one.

Thank you!!!

jhonny_yang · Post by **jhonny_yang** » Fri Nov 19, 2004 5:20 pm

why this problem comes to prime number? that's a faktorial .. using bignum library to solve this prob. it's easy

Boss · Post by **Boss** » Tue Nov 30, 2004 5:48 pm

Hi branka i have the same problem, please tellme how solve the "You must read until the end of the file." in JAVA !!!

wainting for your soon answer, greetings Boss.

Boss · Post by **Boss** » Tue Nov 30, 2004 6:00 pm

Hi !!! in this problem i have a restlessness.
what is mean :: "You must read until the end of the file."

my program is in java, normaly i read from System.in.read();
but, if i must to read from a file, how is the name of the file ???
System.in by default is keyboard

waiting for yours soon answer, greetings Boss !!

Ghust_omega · Post by **Ghust_omega** » Tue Nov 30, 2004 9:08 pm

HI !! to all here a topic that can be usefull
http://online-judge.uva.es/board/viewto ... e9f0d2617d

This topic ist about java I generaly dont code in java but I see this and I believe maybe helps
Hope it Helps
Keep posting !!

Sedefcho · Post by **Sedefcho** » Fri Jan 28, 2005 2:22 pm

Can somebody give any test cases.

How should we round the percentages ( the answers ).
If we have
37.568% should we print 37.56 or 37.57

OJ Board

10200 - Prime Time

thanxxxxxxxxxxxxxxx

10200 Prime Time

Wrong Approach

Gratitude

10200 - Prime Time

10200, What does it mean???????