Prime numbers satisfy another property. If one has three integers m,n and k, we

Question

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 instance, the numbers 19 and 47 are congruent modulo 7 since 19 = 2×7+5 and 47 = 6×7+5. The remainder from division of both 19 and 47 by 7 is 5. The congruence relation is preserved by arithmetic operations. If m1 n1( modk)andm2 n2( modk),thenm1+m2 n1+n2( modk)andm1m2 n1n2( mod k). Prime numbers and congruences are related. There is a theorem that states: If p is a prime number, then ap a( modp) (1) for any integer p > a > 0. For instance, for p = 3, we observe 13 = 11( mod3) (2) 23 = 82( mod3) (3) 33 = 273( mod3) (4) 43 = 644( mod3) (5) (6) Therefore, p = 3 satisfies ap a( mod p). Here, 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 input 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 check.

3. Compare the list of the first 200 primes from your nPrimes function and compare them with the output from your nPrimeLike function. What conclusions can you draw? Your comparison must be quantitative and also avoid large output text. Use list comprehensions or write your own code to filter out elements which may be different in the two lists. If you don’t see any difference push harder to n = 500.(Look up Carmichael numbers) Tip: To calculate the remainder of the division of an with k, use (a**n) %k. For speed, you can also use pow(a,n,k) which does the same. The function pow(a,n) just returns an. (THANKS IN ADVANCE)

Explanation / Answer

1 .

#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

3rd part :

I dont have any prior information about nPrimes Function and the in the question it is also not mentioned , so i dont have enough information to answer this question.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.