Tweet
Đề bài là tìm số nguyên tố thứ n. n<10000, thời gian 1s.
Input N
Ouput M
VD
Input
3
Output
5
---
Em mới làm xong, không biết có cách nào tối ưu hơn được nữa không ạ?
Code bên dưới với n<3600, t<1s, nhưng n>3600, t>1s
Anh chị xem giùm, chỉ dẫn em với ạ.
Input N
Ouput M
VD
Input
3
Output
5
---
Em mới làm xong, không biết có cách nào tối ưu hơn được nữa không ạ?
Code bên dưới với n<3600, t<1s, nhưng n>3600, t>1s
Anh chị xem giùm, chỉ dẫn em với ạ.
PHP Code:
#include <stdio.h>
#include <stdlib.h>
char* inputDirect= "input.txt";
char* outputDirect= "output.txt";
int numIn;
int length;
int* numArr;
int IsPrime(int num);
void ReadInput();
void WriteOutput();
int main()
{
ReadInput();
length= numIn*numIn;
numArr= (int*)calloc(length,sizeof(int));
long int i, j;
for(i=0;i<length;i++)
{
numArr[i]= 1;
}
for(i=2;i*i<=length;i++)
{
if(numArr[i]==1)
{
for(j=i;i*j<=length;j++)
{
numArr[i*j]=0;
}
}
}
WriteOutput();
return 0;
}
void ReadInput()
{
FILE* f= fopen(inputDirect,"r");
if(f)
{
fscanf(f,"%d",&numIn);
fclose(f);
}
}
void WriteOutput()
{
int i, count= 0;
FILE* f= fopen(outputDirect,"w");
if(f)
{
for(i=2;i<length;i++)
{
if(numArr[i]==1)
{
count++;
}
if(count==numIn)
{
fprintf(f,"%d",i);
fclose(f);
return;
}
}
fprintf(f,"-1");
fclose(f);
}
}
int IsPrime(int num)
{
if(num<2)
{
return 0;
}
if(num==2)
{
return 1;
}
if(num%2==0)
{
return 0;
}
int i;
for(i=3;i*i<=num;i+=2)
{
if(num%i==0)
{
return 0;
}
}
return 1;
}
... Nhưng mà nói đi thì phải nói lại, tốc độ xử lý Chip CPU nó lên tới hàng GHz nên kể ra thì người xài PC, cũng chả ai rỗi hơi đi để ý để thấy sự khác biệt của 2 cách này, nhưng mà tại mình làm trên mấy dòng "con nhà nghèo" như 8051, PIC, ARM tốc độ xử lý vài chục MHz, ram cũng chỉ cỡ vài KB à nên phải tiết kiệm :-p.
có gì đâu mà nặng lời... cái này là do mình học KTMT, làm việc với vi điều khiển quen rồi, mà chủ yếu là viết dạng firmware nên gợi ý như thế. Trên vi điều khiển thì không có sung sướng như trên PC nên mình chỉ đưa ra một số ý kiến thế thôi. Còn vấn đề bạn nói, ừ đúng nhưng nó không liên quan gì đến chuyện mình đề cập. Cái mình nói là cách thức làm việc của CPU khi gặp lệnh + và <<, còn cache với bus lại là chuyện khác, đó chỉ là 1 trong hàng tá cái người ta tích hợp vào CPU để tăng tốc xử lý, như bộ tiên đoán lệnh, CacheL1,L2,L3, MMU... thậm chí ngay cả ALU cũng đc thêm vào hàng tá thứ chứ không chỉ có mạch cộng/trừ như 8086(bộ xử lý dấu chấm động...) nhưng có thêm thế nào thì CPU vẫn là CPU và cơ chế hoạt động của nó đến bây giờ vẫn vậy 
Comment