作者longted2 (阿德)
看板Programming
標題[問題] 想請問一下uva 10200 質數問題
時間Mon Jun 25 01:10:59 2012
我想請問一下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
1F：推 whereweare:try to post to Board Prob_Solve 220.228.56.40 06/26 09:44
2F：→ tonyhcc:google 篩法 219.68.140.46 06/28 01:45
3F：→ tonyhcc:和建表 219.68.140.46 06/28 01:47