TAT2808
Búa Gỗ
Em mới học ngôn ngữ lập trình C với ý định làm 1 ứng dụng đơn giản để kiểm tra nếu một số là số nguyên tố Mersenne (Trước đây em có dùng python nhưng nghe nói C/C++ chạy nhanh hơn Python gấp 400 lần). Em sử dụng phương pháp Lucas-Lehmer để kiểm tra (Em muốn test một con số cực lớn). Đây là mà code mà em đã làm (Em có sử dụng GMP để tính những con số rất lớn) :
```
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <math.h>
#include <gmp.h>
int lucas_lehmer(unsigned long int p) {
mpz_t M, s, t;
// Let M = 2^p - 1
mpz_init_set_ui(t, p);
mpz_init(M);
mpz_setbit(M, p);
mpz_sub_ui(M, M, 1);
unsigned long int i;
mpz_init_set_ui(s, 4);
for (i = 3; i <= p; i++) {
printf("Processed: %d\n", i-3);
mpz_mul(s, s, s);
mpz_sub_ui(s, s, 2);
/* mpz_mod(s, s, mp) but more efficiently done given mod 2^p-1 */
if (mpz_sgn(s) < 0) mpz_add(s, s, M);
/* while (n > mp) { n = (n >> p) + (n & mp) } if (n==mp) n=0 */
/* but in this case we can hase at most one loop plus a carry */
mpz_tdiv_r_2exp(t, s, p);
mpz_tdiv_q_2exp(s, s, p);
mpz_add(s, s, t);
while (mpz_cmp(s, M) >= 0) mpz_sub(s, s, M);
}
int res;
res = !mpz_sgn(s);
mpz_clear(t); mpz_clear(M); mpz_clear(s);
return res;
}
int main() {
unsigned long int p;
printf("Enter an exponent:");
scanf("%d", &p);
if (lucas_lehmer(p)) {
printf("\nPrime number: True\n");
}
else {
printf("\nPrime number: False\n");
}
system("pause");
return 0;
}
```
Em compile và run ứng dụng thì nó chạy khá ổn. Nhưng khi cho input là 1 số rất lớn (ví dụ như 33301033) thì nó chạy khá là chậm (Trung bình khoảng 5 giây mới lên được 1 số). Có cách nào để nó chạy nhanh hơn không ạ, ít nhất là có thể khoảng 150 số/giây (em thì mong được 500 số/giây, nhưng nếu không thể thì 150 số/giây cũng được).
P/S: Em có nhận ra 1 điều là ứng dụng của em khi chạy chỉ sử dụng 1 luồng (trong khi máy em có 4 luồng)
```
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <math.h>
#include <gmp.h>
int lucas_lehmer(unsigned long int p) {
mpz_t M, s, t;
// Let M = 2^p - 1
mpz_init_set_ui(t, p);
mpz_init(M);
mpz_setbit(M, p);
mpz_sub_ui(M, M, 1);
unsigned long int i;
mpz_init_set_ui(s, 4);
for (i = 3; i <= p; i++) {
printf("Processed: %d\n", i-3);
mpz_mul(s, s, s);
mpz_sub_ui(s, s, 2);
/* mpz_mod(s, s, mp) but more efficiently done given mod 2^p-1 */
if (mpz_sgn(s) < 0) mpz_add(s, s, M);
/* while (n > mp) { n = (n >> p) + (n & mp) } if (n==mp) n=0 */
/* but in this case we can hase at most one loop plus a carry */
mpz_tdiv_r_2exp(t, s, p);
mpz_tdiv_q_2exp(s, s, p);
mpz_add(s, s, t);
while (mpz_cmp(s, M) >= 0) mpz_sub(s, s, M);
}
int res;
res = !mpz_sgn(s);
mpz_clear(t); mpz_clear(M); mpz_clear(s);
return res;
}
int main() {
unsigned long int p;
printf("Enter an exponent:");
scanf("%d", &p);
if (lucas_lehmer(p)) {
printf("\nPrime number: True\n");
}
else {
printf("\nPrime number: False\n");
}
system("pause");
return 0;
}
```
Em compile và run ứng dụng thì nó chạy khá ổn. Nhưng khi cho input là 1 số rất lớn (ví dụ như 33301033) thì nó chạy khá là chậm (Trung bình khoảng 5 giây mới lên được 1 số). Có cách nào để nó chạy nhanh hơn không ạ, ít nhất là có thể khoảng 150 số/giây (em thì mong được 500 số/giây, nhưng nếu không thể thì 150 số/giây cũng được).
P/S: Em có nhận ra 1 điều là ứng dụng của em khi chạy chỉ sử dụng 1 luồng (trong khi máy em có 4 luồng)
