#include<bits/stdc++.h> //O(nlogn)? using namespace std; bool prime(int n){ if(n==2) return true; for(int i=2;i*i<=n;i++){ if(n%i==0){ return false; } } return true; } int main(){ int n; cin>>n; int a[10005]; a[0]=1; a[1]=1; for(int i=2;i<=n;i++){ a[i]=a[i-1]+a[i-2]; if(prime(a[i])){ cout<<a[i]<<" "; } } cout<<endl; for(int i=0;i<n;i++){ cout<<a[i]<<" "; } return 0; }