(A prime number, p, is called a Sophie Germain Prime if both p and 2p+1 are prim
ID: 3817826 • Letter: #
Question
(A prime number, p, is called a Sophie Germain Prime if both p and 2p+1 are primes. The first few Sophie Germain Primes are 2, 3, 5, 11, 23, 29, 41, 53, 83, 89, 113, 131, etc. It is not known whether there are an infinite number of such primes. The largest known Sophie Germain prime is 79911 decimal digits long)
Write a program to investigate the distribution of Sophie Germain Primes.Write a C program that reads an integer number, say r. It then computes and outputs a table with the number of Sophie Germain Primes less than 10, 10^2, 10^3, … 10^r.
For example if r is 5 it should output:
3
10
37
190
1171
Test the program for different values for r.
To simplify the problem we could split it into smaller pieces by defining functions. One function that would be useful would be a function called isPrime. That function would take an integer argument, n, and return 1 if n is a prime number and 0 otherwise. Another useful function would be countValues which takes an integer argument, say and returns the number of Sophie Germain primes less than k.
The program must actually test numbers for primality and count the number of primes that are Sophe Germain primes. It must not just output the final results by obtaining them from other sources.
Explanation / Answer
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int isPrime(int n, int m)
{
int flag=0,i;
for(i=2; i<=n/2; ++i) // checking for number
{
if(n%i==0)
{
flag=1;
break;
}
}
for(i=2; i<=m/2; ++i) // checking for number double+1
{
if(m%i==0)
{
flag=1;
break;
}
}
if (flag==0){
return 1;
}
else
return 0;
}
int main()
{ int r,ans=0,i,j,count=0;
double p;
printf("Enter a number: ");
scanf("%d",&r);
for(i=1;i<=r;i++ )
{ p=pow(10,i);
for(j=2;j<p;j++)
{
count+=isPrime(j,(2*j)+1); // passing numbers for Sophie Germain Prime
}
printf("%d ",count);
count = 0; //reinitialising count to zero inorder to avoiod redundant counts
}
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.