tcfsh910993
(Akito-senior)
學校
:
國立臺中第一高級中學
編號 : 14969
來源 : [114.43.212.110]
最後登入時間 ：
2023-09-19 16:28:37
此題是否改的太誇張了點，用一般迴圈的方式一定TLE，這對新手來說太難了
這題只能先建質數表才能AC
我用d905的程式來解此題要 1 sec, 解d905只要 300多ms，測資也太多了吧
完全同意，我說說我這個新手發生的情況吧
首先我用了最簡單的迴圈，當然sqrt是有放的(我對整數論算是小有研究)，然後...吃TLE。
然後我把迴圈進化成測完2和3之後就只測6k+1和6k+5型的數字，於是程式變成了附(一)的樣子
這樣子已經可以在當我輸入2147483647的時候，在我無法察覺的時間內輸出"質數"兩字
結果還是吃TLE@@
最後我就看了大大的建議寫了質數表
結果...唉我這個新手只會宣告數組，然後就爆掉囉@@
程式見附(二)
附(一)
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
main()
{
int a;
int con;
int jud;
int con_2;
while(scanf("%d",&a)!=EOF)
{
jud=0;
con_2=0;
if(a%2==0)
jud=jud+1;
if(a%3==0)
jud=jud+1;
for(con=5;con<=sqrt(a)&&jud==0;)
{
if(a%con==0)
jud=jud+1;
if(con_2==0)
{
con=con+2;
con_2++;
}
else if(con_2==1)
{
con=con+4;
con_2--;
}
}
if(jud==0)
printf("質數\n");
else
printf("非質數\n");
}
return 0;
}
附(二)
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define N 2147483647
main()
{
int a[N];
int con;
long int con_2;
int n;
for(con=2;con<=N;con++)
{
a[con]=0;
}
a[1]=1;
for(con=2;con<=sqrt(N);con++)
{
if(a[con]==0)
{
for(con_2=con*con;con_2<=N;con_2=con_2+con)
{
a[con_2]=1;
}
}
}
while(scanf("%d",&n)!=EOF)
{
if(a[n]==0)
printf("質數\n");
else if(a[n]==1)
printf("非質數\n");
}
return 0;
}
明天再學新招破這題~順便破d705~
此題是否改的太誇張了點，用一般迴圈的方式一定TLE，這對新手來說太難了
這題只能先建質數表才能AC
我用d905的程式來解此題要 1 sec, 解d905只要 300多ms，測資也太多了吧
完全同意，我說說我這個新手發生的情況吧
首先我用了最簡單的迴圈，當然sqrt是有放的(我對整數論算是小有研究)，然後...吃TLE。
然後我把迴圈進化成測完2和3之後就只測6k+1和6k+5型的數字，於是程式變成了附(一)的樣子
這樣子已經可以在當我輸入2147483647的時候，在我無法察覺的時間內輸出"質數"兩字
結果還是吃TLE@@
最後我就看了大大的建議寫了質數表
結果...唉我這個新手只會宣告數組，然後就爆掉囉@@
程式見附(二)
附(一)
#include
#include
#include
main()
{
int a;
int con;
int jud;
int con_2;
while(scanf("%d",&a)!=EOF)
{
jud=0;
con_2=0;
if(a%2==0)
jud=jud+1;
if(a%3==0)
jud=jud+1;
for(con=5;con<=sqrt(a)&&jud==0;)
{
if(a%con==0)
jud=jud+1;
if(con_2==0)
{
con=con+2;
con_2++;
}
else if(con_2==1)
{
con=con+4;
con_2--;
}
}
if(jud==0)
printf("質數\n");
else
printf("非質數\n");
}
return 0;
}
附(二)
#include
#include
#include
#define N 2147483647
main()
{
int a[N];
int con;
long int con_2;
int n;
for(con=2;con<=N;con++)
{
a[con]=0;
}
a[1]=1;
for(con=2;con<=sqrt(N);con++)
{
if(a[con]==0)
{
for(con_2=con*con;con_2<=N;con_2=con_2+con)
{
a[con_2]=1;
}
}
}
while(scanf("%d",&n)!=EOF)
{
if(a[n]==0)
printf("質數\n");
else if(a[n]==1)
printf("非質數\n");
}
return 0;
}
明天再學新招破這題~順便破d705~
sqrt(2147183647) 差不多是46340，考慮到0再加個保險，設 N=46345 就不會爆了
我也是建質數表之後才AC的
以下是我TLE的code
#include<cstdio>
#include<cmath>
int main()
{
int input, counter;
while( scanf( "%d", &input ) != EOF )
{
int limit = (int)sqrt( input );
for( counter = 2; counter <= limit; counter++ )
if( input % counter == 0 )
{
printf( "非質數\n" );
break;
}
if( input % counter || input == 2 )
printf( "質數\n" );
}
return 0;
}
即使一筆測資只開了一次根號還是會超時,所以一般的判斷法可能無法使用,可能還是只有建表一途吧
卻說我還滿想知道4ms就AC的解法是什麼...
我也是建質數表之後才AC的
以下是我TLE的code
#include
#include
int main()
{
int input, counter;
while( scanf( "%d", &input ) != EOF )
{
int limit = (int)sqrt( input );
for( counter = 2; counter <= limit; counter++ )
if( input % counter == 0 )
{
printf( "非質數\n" );
break;
}
if( input % counter || input == 2 )
printf( "質數\n" );
}
return 0;
}
即使一筆測資只開了一次根號還是會超時,所以一般的判斷法可能無法使用,可能還是只有建表一途吧
卻說我還滿想知道4ms就AC的解法是什麼...
以前的測資是有能可 4ms以下就AC，改版後是不太可能出現
我的是1S AC, 看到有人224ms，我也很想知道到底是用什麼方法做
tcfsh910993
(Akito-senior)
學校
:
國立臺中第一高級中學
編號 : 14969
來源 : [114.43.212.110]
最後登入時間 ：
2023-09-19 16:28:37
我也是建質數表之後才AC的
以下是我TLE的code
#include
#include
int main()
{
int input, counter;
while( scanf( "%d", &input ) != EOF )
{
int limit = (int)sqrt( input );
for( counter = 2; counter <= limit; counter++ )
if( input % counter == 0 )
{
printf( "非質數\n" );
break;
}
if( input % counter || input == 2 )
printf( "質數\n" );
}
return 0;
}
即使一筆測資只開了一次根號還是會超時,所以一般的判斷法可能無法使用,可能還是只有建表一途吧
卻說我還滿想知道4ms就AC的解法是什麼...
以前的測資是有能可 4ms以下就AC，改版後是不太可能出現
我的是1S AC, 看到有人224ms，我也很想知道到底是用什麼方法做
我現在建了質數表,1.1s過d705,但這題還是TLE...
這題真的太誇張了...
此題是否改的太誇張了點，用一般迴圈的方式一定TLE，這對新手來說太難了
這題只能先建質數表才能AC
我用d905的程式來解此題要 1 sec, 解d905只要 300多ms，測資也太多了吧
此題是否改的太誇張了點，用一般迴圈的方式一定TLE，這對新手來說太難了
這題只能先建質數表才能AC
我用d905的程式來解此題要 1 sec, 解d905只要 300多ms，測資也太多了吧
聽說JAVA的Thread因平行處理而聞名
所以小弟試著用Thread制作出一個判斷質數的程式
我的做法是建了兩個Thread，一個從2找上去(2.3.4....)，一個從開根號的地方開始找回來 (n, n-1, n-2....)
但是貌似系統不能讓我使用class的field空間 +_____+
有沒有大大能幫我測試一下這個想法有沒有比較快...
或者幫我轉成符合系統需求的code...
我想知道這個想法可不可行(減少運算時間 這方面)。
import java.util.Scanner;
public class A007_2{
int test1, test2;
int flag1 = 1, flag2 = 1;
int limit, num;
public Rb1 r1 = new Rb1();
public Rb2 r2 = new Rb2();
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int num;
A007_2 t = new A007_2();
while (cin.hasNext()) {
Thread td1 = new Thread(t.r1);
Thread td2 = new Thread(t.r2);
num = cin.nextInt();
int limit = (int)Math.sqrt(num) +1;
t.setNum(num);
t.setLimit(limit);
t.setTest1(2);
t.setTest2(limit);
t.setFlag1(1);
t.setFlag2(1);
td1.start();
td2.start();
while(td1.isAlive() || td2.isAlive()){};
if(t.getFlag1()==1 && t.getFlag2() == 1)
System.out.println("質數");
else
System.out.println("非質數");
}
}
public void setLimit(int l){
limit = l;
}
public void setNum(int n){
num = n;
}
public int getTest2(){
return test2;
}
public void setTest1(int t1){
test1 = t1;
}
public void setTest2(int t2){
test2 = t2;
}
public void setFlag1(int f){
flag1 = f;
}
public void setFlag2(int f2){
flag2 = f2;
}
public int getFlag1(){
return flag1;
}
public int getFlag2(){
return flag2;
}
private class Rb1 implements Runnable{
public void run(){
for(; test2>=test1; test2 --){
if(num%test2 == 0 && num !=2){//System.out.println("in Rb1");
flag2 = 0;
break;
}
}
}
}
private class Rb2 implements Runnable{
public void run(){
for(; test1<=test2; test1++){
if(num%test1 == 0 && num !=2){//System.out.println("in Rb2");
flag1=0;
break;
}
}
}
}
}
此題是否改的太誇張了點，用一般迴圈的方式一定TLE，這對新手來說太難了
這題只能先建質數表才能AC
我用d905的程式來解此題要 1 sec, 解d905只要 300多ms，測資也太多了吧
個人做了一點測資來測試一下我上面所寫的程式(個人寫的程式都是JAVA 以下為class名)：
TestData --> 使用Random產生1500組測資
A007 --> 使用一般迴圈法。要檢測的數字從2~原數開根號，先用if濾掉2，
再進入for迴圈，for的index每次都加2，(也就是只檢查奇數: 3, 5, 7.....)
** 另外我還寫個陣列紀錄檢測過的數字，
for裡面放個if，用以判斷接下來要檢測的數字是否為之前檢測過的數字的倍數
若是，則直接跳過不用計算。(比如先前已經檢測過7，再來只要遇到21,35,49....都會跳過)
A007_2 --> 使用Thread法。兩個Thread，一個從頭找上去，一個從原數開根號找回來，
會合了就統整結果。
Checking --> A007和A007_2會分別輸出各自的1500個結果成一個檔案，
再由這個class判斷兩個檔案的答案是否相同。
得到的 評測數據：
A007： time spent: 17645 (ms) ----> GG (17秒 ORZ)
A007_2： time spent: 779 (ms) ---> GJ (還沒1秒)
Checking: Correct! ---> (兩個輸出的1500個結果完全一模一樣!)
以上報告...，我還是無法把A007_2寫成符合系統要求的，
明天在繼續了。
歡迎各位大大指教，有興趣可以跟我要code。