题目描述
幸运数是波兰数学家乌拉姆命名的。它采用与生成素数类似的“筛法”生成
。
首先从1开始写出自然数1,2,3,4,5,6,....
1 就是第一个幸运数。
我们从2这个数开始。把所有序号能被2整除的项删除，变为：
1 _ 3 _ 5 _ 7 _ 9 ....
把它们缩紧，重新记序，为：
1 3 5 7 9 .... 。这时，3为第2个幸运数，然后把所有能被3整除的序号位置的数删去。注意，是序号位置，不是那个数本身能否被3整除!! 删除的应该是5，11, 17, ...
此时7为第3个幸运数，然后再删去序号位置能被7整除的(19,39,...)
最后剩下的序列类似：
1, 3, 7, 9, 13, 15, 21, 25, 31, 33, 37, 43, 49, 51, 63, 67, 69, 73, 75, 79, ...
思路
一开始以为是考数学，没啥思路，，看题解才知道还真是用链表模拟，不过C语言的题解比较少，我来贡献一个吧。
链表模拟说简单也简单，说复杂也挺复杂。链表本身的关键点其实只有一个：记录当前结点的前一个结点，然后很多操作都可以很方便了，比如删除当前结点。
本题思路的话就是：先构建一个包含1~m-1的链表。不断循环遍历链表，pos记录遍历的链表结点的下标，然后fuckynod（哈哈，我的恶趣味）记录当前的幸运数结点，fuckypos记录需要整除的数（其实就是fuckynod->val），然后把所有整除的pos结点都从链表中删除即可（删除需要记录当前结点的前一个结点pre）。直到找不到非幸运的数就停止，最后留下来的所有大于n，小于m的数个数输出即可。
代码
#include<bits/stdc++.h>
using namespace std;
int n,m;
struct node{
int val;
node* next;
node(int k):val(k),next(nullptr){}
};
void removefucky(node*head){
int fuckypos=2;
node* fuckynod=head->next;
int pos=1;
while(1){
node* nod=head->next;
node* pre=head;
pos=1;
int flag=0;
while(nod!=nullptr){
if(pos%fuckypos==0){
pre->next=nod->next;
flag=1;
}else pre=nod;
nod=nod->next;
pos++;
}
if(!flag){
break;
}
fuckynod=fuckynod->next;
fuckypos=fuckynod->val;
}
}
int main(){
cin>>n>>m;
node*head=new node(-1);
node*tail=nullptr;
for(int i=1;i<m;i++){
node*nod=new node(i);
if(tail==nullptr){
head->next=nod;
tail=nod;
}
else {
tail->next=nod;
tail=nod;
}
}
removefucky(head);
node* nod=head->next;
int ans=0;
while(nod!=nullptr){
if(nod->val>n)
ans++;
nod=nod->next;
}cout<<ans;
}