[問題] 想請問一下uva 10200 質數問題

看板Programming作者longted2 (阿德)時間13年前 (2012/06/25 01:11)推噓1(1推 0噓 2→)

留言3則, 2人參與討論串1/1

我想請問一下uva 10200 prime time 的這一題..我本來是用暴力法來檢查是否是質數.....但是這樣子time complexity會很高...所以我爬了一下網路採用別人的寫法 time complexity 是有很大的改進.....但是uva還是回應time limit execed...但是我看了一下我的程式碼...我不知道問題出在哪...想請高手給個意見以下是我的souce code // Q10200 Prime Time.cpp : 定義主控台應用程式的進入點。 // //#include "stdafx.h" #include <stdio.h> //#include <conio.h> #include <stdlib.h> #include <string.h> #include <math.h> #define buffer_Size 256 void Prime_Time(int a,int b); bool Check_Prime(int result); char *Forma_Data(double data); float round(float num,int location) { int sub=1,B; for(int i=0;i<location;i++) { sub*=10; } int num2=sub*10; B=(num+(float)5/num2)*sub; num=(float)B/sub; return num; } int main() { /* int a=40; double b=41; double fv=(double)((int)(a*100)/b);//a*100/b; printf("%f\n",fv); */ char buffer[buffer_Size]; //FILE *fp=fopen("test.txt","r"); bool Get_Test_Data=false; int a,b=0; while (fgets(buffer, buffer_Size, stdin)) { char *pch = strtok (buffer," "); while (pch != NULL) { if(Get_Test_Data==false) { a=atoi(pch); Get_Test_Data=true; } else { b=atoi(pch); Get_Test_Data=false; } //printf ("%s\n",pch); pch = strtok (NULL, " ,.-"); } if((0<=a && a<b && a<=10000) &&(0<=b && a<b && b<=10000)) { Prime_Time(a,b); } } // getch(); return 0; } void Prime_Time(int a,int b) { /* int a=40; double b=41; double fv=(double)((int)(a*100)/b);//a*100/b; printf("%f\n",fv); */ int count=0; for(int i=a;i<=b;i++) { //printf("%d\n",i); double temp_pow=pow((double)i, 2); int result=temp_pow+i+41; bool check=Check_Prime(result); if(check==true) { count++; } } double final_result=(double)((int)(count*100)/(double)(b-a+1)); double Input_format_data=round(final_result,2); char *Get_result=Forma_Data(Input_format_data); //getch(); printf("%s\n",Get_result); } char *Forma_Data(double data) { char temp[256]={NULL}; sprintf(temp,"%f",data); int str_len=strlen(temp); int dot_index=0; char result_char[buffer_Size]={NULL}; for(int i=0;i<str_len;i++) { if(temp[i]=='.') { dot_index=i; break; } } for(int i=0;i<=dot_index+2;i++) { result_char[i]=temp[i]; } //double result=atof(result_char); //sscanf(result_char,"%E",result); return result_char; } bool Check_Prime(int result) { if(result%2==0 || result%3==0) { return false; } for(int i=3;i*i<=result;i+=2) { if(result%i==0) { return false; } } return true; } /* if(result==1) { return false; } for(int i=2;i<result;i++) { if(result%i==0) { return false; } } return true; */ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.231.67.179