Part 3 Prime numbers satisfy another property. If one has three integers m, n an
ID: 3747003 • Letter: P
Question
Part 3 Prime numbers satisfy another property. If one has three integers m, n and k we say m and n are congruent modulo k if the remainder from dividing m by k is the same as the remainder from dividing n by k. We can then write m n mod k). For istance, the numbers 19 and 47 are congruent modulo 7 since 19 = 2 x 7+5 and 47-6 × 7 + 5. The remainder from division of both 19 and 7 by 7 is5 The congruence relation is preserved by arithmetic operations. If mE nI mod k) and m2 n2 mod k), thenmm2 n2( mod k) and mim2 n2 mod k) Prime numbers and congruences are related. There is a theorem that states If p is a primebe hen aP mod p) for any integer p> a > 0. For instance, for p 3, we observe 28 2( mod 3) 3327 3( mod 3) 4644 mod 3) Therefore, p = 3 satisfies ap-a( mod p). llere, we have tried out a = 1,2,3, 4 although 4 is not guaranteed to work. This relation does not in general hold true for composite numbers. 1. Write a function listPrimeLike (n) which accepts n as an iput and returns the list of prime-like numbers less than n using the congruence relation check 2. Write a function nPrimeLike (n) which accepts n as an input and re turns the first n number of prime-like numbers using the congruence rela- tion chock.Explanation / Answer
#include<stdio.h>
int min(int a, int b) {
if (a > b) {
return b;
}
return a;
}
void isPrimeLike(int n) {
int i;
int j;
int k;
for (i = 1; i < n; i++) {
for (j = 1; j < n; j++) {
for (k = 2; k <= min(i, j); k++) {
if(i % k == j % k && i != j && (i % j != 0 && j % i != 0)) {
printf("%d %d %d ",i,j,k);
}
}
}
}
}
int main()
{
int n;
scanf("%d",&n);
isPrimeLike(n);
return 0;
}
Output Format - Every line contains three integers m , n and k where m % k == n % k
This code is written in c language . Use any gcc compiler to compile and run and provide any integer as input.
2nd part -
#include<stdio.h>
#include<limits.h>
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int min(int a, int b) {
if (a > b) {
return b;
}
return a;
}
void isPrimeLike(int n) {
int i;
int j;
int k;
set <int> s;
for (i = 1; i < INT_MAX; i++) {
for (j = 1; j < INT_MAX; j++) {
for (k = 2; k <= min(i, j); k++) {
if(i % k == j % k && i != j && (i % j != 0 && j % i != 0)) {
//printf("%d %d %d ",i,j,k);
s.insert(i);
s.insert(j);
}
}
}
}
set<int> :: iterator it;
vector<int> v;
for (it = s.begin(); it != s.end(); it++) {
v.push_back(*it);
}
sort(v.begin(),v.end());
for(i = 0; i < n; i++) {
printf("%d ", v[i]);
}
printf(" ");
}
int main()
{
int n;
scanf("%d",&n);
isPrimeLike(n);
return 0;
}
The above solution is wriiten in C++. please refer to the solution. and input n value in the int range.
Output : first n unique primelike numbers