作者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