C   70
prime
Guest on 11th February 2023 01:19:59 AM


  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<math.h>
  4. struct node{
  5.     int no;
  6.     struct node *next;
  7. };
  8. int prime[5000],nprime;
  9. int main(){
  10.     int i,j;
  11.     int sq;
  12.     int check;
  13.     int n;
  14.     int cut,count;
  15.     struct node *member,*ptr,*current;
  16.     prime[0]=2;
  17.     nprime=1;
  18.     for(i=3;nprime<=3502;i+=2){
  19.         check=1;
  20.         sq=sqrt(i);
  21.         for(j=3;j<=sq;j+=2){
  22.             if(i%j==0){
  23.                 check=0;
  24.                 break;
  25.             }
  26.         }
  27.         if(check==1){
  28.             prime[nprime++]=i;
  29.         }
  30.     }
  31.     while(1){
  32.         scanf("%d",&n);
  33.         if(n==0)break;
  34.         if(n==1){printf("1\n");continue;}
  35.         member=(struct node*)malloc(sizeof(struct node));
  36.         member->no=1;
  37.         member->next=NULL;
  38.         current=member;
  39.         for(i=2;i<=n;i++){
  40.             ptr=(struct node*)malloc(sizeof(struct node));
  41.             current->next=ptr;
  42.             ptr->no=i;
  43.             ptr->next=NULL;
  44.             current=ptr;
  45.         }
  46.         current->next=member;
  47.         /*current=member;*/
  48.         count=0;
  49.         while(n>1){
  50.             cut=prime[count++];
  51.             /*if(count==1)cut--;*/
  52.             cut = (cut-1) % n + 1;
  53.             /*printf("(%d)",cut);*/
  54.             while(cut--){
  55.                 ptr=current;
  56.                 current=current->next;
  57.             }
  58.             /*printf("[%d]\n",current->no);*/
  59.             ptr->next=current->next;
  60.             /*free(current);*/
  61.             current=ptr;
  62.             n--;
  63.         }
  64.         printf("%d\n",ptr->no);
  65.     }
  66.     getchar();
  67.     return 0;
  68. }
Raw Paste

Login or Register to edit or fork this paste. It's free.