Code xuất ra số Fibonaci lớn nhất là số nguyên tố và nhỏ hơn n

#1

Mọi người cho mình hỏi đoạn code này đã đúng và tối ưu chưa ạ ? :blush:

#include<bits/stdc++.h>
using namespace std;
bool fb(int n)
{int f0=1;
int f1=1;
int fn=0;
if(n<=1) return false;
while(fn<=n)
    {fn=f0+f1;
    f0=f1;
    f1=fn;
    if(fn==n) return true;
    }
    return false;
}
bool snt(int x)
{if (x<2) return false;
else if (x==2) return true;
else if (x%2==0) return false;
for (int i=3;i<=sqrt(x);i+=2)
    {if (x%i==0) return false;
    }
    return true;
}
int fibosnt(int a[], int n)
{int max=0;
for (int i=0;i<n;i++)
    {if (fb(i)==true && snt(i)==true)
        {if (max<i) max=i;
        }
    }
    return max;
}
int main()
{freopen("fibo.inp","r",stdin);
freopen("fibo.out","w",stdout);
int n,a[100];
cout<<"nhap n:"; cin>>n;
cout<<fibosnt(a,n);
return 0;
}
#2

Hàm fb() có thể giảm được khá nhiều bằng cách dùng tính chất của số fibonacy. :slight_smile:

n là số fibonacy thì 5n2 + 4 hoặc 5n2 - 4 là số chính phương.

Vòng for trong snt() có thể thay i<=sqrt(x) thành i * i <= x. :slight_smile:

Hàm fibosnt()

if (fb(i)==true && snt(i)==true)

Do fb() và snt() là bool sẵn rồi, chỉ cần xài như vầy là được rồi. :slight_smile:

if (fb(i) && snt(i))

Trong main() sao không có chỗ nhập mảng a[] nhỉ. :slight_smile:

3 Likes
#3

Nhanh nhất là tính riêng sqrt t = sqrt(x) rồi i <= t :slight_smile:

5 Likes
#4

Làm vậy nó lòi ra một dòng, xấu. :kissing:

3 Likes
#5

Số nhỏ hơn n chứ không phải trong mảng có số lượng phần tử là n bạn ơi :slight_smile:

#6

Thì viết nó ngay trong phần khởi tạo của for :slight_smile:

4 Likes
#7

Vậy truyền a[] vào để làm gì, còn khai báo a[100] nữa. Thừa stack. :thinking:

2 Likes
#8

Lúc đầu làm trong mảng sau đọc lại đề rồi quên xóa a[] luôn :))

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?