How many integers from 1 to 1 0 0 inclusive can be written as the product of two (not necessarily distinct) primes?
If you can find a computer science or combinatorics approach, post your solution!
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
I used the method of listing the primes, and finding numbers with exactly 4 factors. This totaled to 3 1 . This is when the primes are distinct. If the primes are the same, then the squares of primes must be included. Thus, the squares of 2 , 3 , 5 , 7 are included. Thus, the total I reached was 3 5 .
Could someone point out the mistake in my logic?
Log in to reply
Could be computation. Like you'd already counted a perfect prime square.
I think you just miscounted, there should be 30 numbers that are products of 2 distinct primes. Your logic should be correct, but you could've just counted the numbers with 3 or 4 factors instead.
Did you include 1?
Excellent job! :D
Does that count the repeated operations? (Such as 2x7=7x2)
Since coding is allowed,here is the simplest thing that came to my mind
1 2 3 4 5 6 7 8 9 10 |
|
Brilliant & simple
Brilliant! :D
There's an extra ) after n**.5
I simplified it to between 2-50 but great
Mathematica one liner: Length@Select[Range@100,PrimeOmega@#==2&]
2 Can be Multiplied with all Primes Upto 47.... = 15
3 Can Multiplied with all primes upto 31 except (2).. = 10
5 Can be Upto 19... = 6
7 Can be Upto 13... = 3.....
Adding All we get ::34::
For your problem..the relative rate of change of population would be (1/33-1/46)(say A). So after n years total population will be ((1+A)^n)*Initial population. So (1+A)^n=2... N=log(2)/log(1+A)... n=81.28 ... Rounding off n=82
Mathematica solution:
Length[DeleteDuplicates[ Select[Flatten[ Table[Prime[i] Prime[j], {i, 1, 4}, {j, 1, 15}]], # < 100 &]]]
This gives 34.
Nice.
Or with FactorInteger:
Length@Cases[Total[#[[All, 2]]] & /@ FactorInteger /@ Range[100], 2]
We can split our composite numbers into two varieties: No factors are greater than the square root, or, One factor is greater than the square root.
Finding all of the first variety boils down into finding all possible combinations of two prime numbers lower than the square root of our upper bound. In this case, that number is 10. We have four prime numbers less than ten, competing for two slots, so it ends up evaluating to (n+r-1)!/(n-1)!r! = 5!/3!2!, or 10 ways.
For the second variety, one factor is greater than the square root. As a result, one factor is smaller than the square root. For each of these four factors, we must assess how many numbers they can be multiplied by to get a number below 100. For example, 7 can be multiplied by any number below 15.
7 can be multiplied by 2 numbers above 10. 5 can be multiplied by 4 numbers above 10. 3 can be multiplied by 7 numbers above 10. 2 can be multiplied by 11 numbers above 10.
Overall, this adds up to 10 + 2 + 4 + 7 + 10 = 34.
Define the problem as the product of two primes. Every such product has a left and right factor. let the left factor be necessarily smaller than the right. To find the least upper bound of the left factor, take the square root of 100. This is 10, so the left prime can be at most 7. Next split the problem into four cases since the left factor can only be 2, 3, 5, or 7. Each case shall be defined by the left factor. Now to find the least upper bound of the right factor for each case, divide 100 by each left factor in turn and take the integer part. These results are 50, 33, 20, and 14. There are 6 primes between 2 and 14, 2 between 15 and 20, 3 between 21 and 33, and 4 between 34 and 50. If the left factor is 2, the right factor can be in any of these categories. For each successive case, eliminate the last category from the preceding case. the sum is 40. Now eliminate repeated products, of which there are 6. Therefore, there are 34 possibilities
Didn't check the exact math, but the method you used was perfect. Great job!
how do you determine number of repeats?
The Python sympy library will calculate the prime factors of a number and put them into a dictionary for you.
I honestly just listed all of them out. They are: 4 , 6 , 9 , 1 0 , 1 4 , 1 5 , 2 1 , 2 2 , 2 5 , 2 6 , 3 3 , 3 4 , 3 5 , 3 8 , 3 9 , 4 6 , 4 9 , 5 1 , 5 5 , 5 7 , 5 8 , 6 2 , 6 5 , 6 9 , 7 4 , 7 7 , 8 2 , 8 6 , 8 7 , 9 1 , 9 3 , 9 4 , 9 5 . I'm really interested in finding a cool approach to this problem other than brute force. Note that any prime numbers are automatically disqualified, because remember, 1 isn't prime. Have fun thinking of a better solution, and tell me if I missed any so I can update the answer! :D
@Calvin Lin I'd really appreciate it if you reshared this problem. I think it's really great but I don't want it to fall under the radar like my other problems. Thanks! :D
Listing Out Takes Time,But Still Is A Good WAy!..:)..Worked Here as Well!
I did it the same way
hi, you missed 85=5*17
Using
Ruby
, the following script will give you
34
:
1 2 |
|
A solution in Ocaml: utop # let primes = [2;3;5;7;11;13;17;19;23;29;31;37;41;43;47]
val primes : int list = [2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47]
utop # let divwithmod i j = if (i mod j != 0) then None else Some (i/j);; val divwithmod : int -> int -> int option = <fun>
utop # open List;; ─( 22:45:31 )─< command 3 utop # let deoption a = match a with |Some b -> b |None -> 999;; val deoption : int option -> int = <fun>
utop # let primecheck i = fold_left ( || ) false (map (fun x -> mem (deoption (divwithmod i x)) primes) primes) val primecheck : int -> bool = <fun>
utop # let rec totprime curr tot = if curr >= 100 then tot else if primecheck curr then totprime (curr+1) (tot+1) else totprime (curr+1) tot;; val totprime : int -> int -> int = <fun>
utop # totprime 2 0;;
Simple Python brute force solution:
p = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
print len([m*n for m in p for n in p if m <= n and m*n < 100])
Mathematica code
cont=0;
For[i = 1, Prime[i] <= 100, i++, {For[j = i, Prime[j] <= 100, j++, {
If[Prime[i]*Prime[j] <= 100, cont++]}]}]
cont
Here is a code in Just BASIC:
data 15, 2, 3, 5, 7,11,13,17'we only need 15 primes
data 19,23,29,31,37,41,43,47'from 2 to 47 so that
'no product of smallest and biggest goes above 100
read size:dim primes(size)'size = 15
for i= 1 to size'put 15 primes in primes()
read prime:primes(i)=prime
next i
'making all possible pairs from 15 primes
for first = 1 to size
for second = first to size
product = primes(first) * primes(second)
if product <= 100 then count = count + 1
next second
next first
print "count = ";count
It gives total of 34.
Some Lisp Code:
(length (let ((primes '(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47)))
(mapcon (lambda (sub)
(let ((head (car sub)))
(mapcan (lambda (elt)
(if (<= (* elt head) 100)
(list (cons head elt))))
sub)))
primes)))
Evaluates to 34.
1 2 3 4 5 6 7 8 9 10 11 12 |
|
I run it in C++, little brute force to find the primes,
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|
Here is the VB.NET code I used. Pardon me for my choice of variable names - I admit their pretty bad. Also, I skipped 1 for obvious reasons.
Module Module1
Sub Main()
Dim number_of_numbers_counter As Integer = 0
Dim counter As Integer = 2
Dim counter_2 As Integer = 0
For n = 2 To 100
Dim prime_factors(0) As Integer
Dim n_editable As Integer = n
While Not n_editable = 1
If n_editable Mod counter = 0 Then
n_editable /= counter
prime_factors(counter_2) = counter
ReDim Preserve prime_factors(prime_factors.Length)
counter_2 += 1
Else
counter += 1
End If
End While
ReDim Preserve prime_factors(prime_factors.Length - 2)
If prime_factors.Length = 2 Then
Dim number1 As Integer = prime_factors(0)
Dim number2 As Integer = prime_factors(1)
number_of_numbers_counter += 1
If isPrime(number1) And isPrime(number2) Then
Console.WriteLine(n.ToString + " " + number1.ToString + " " + number2.ToString)
End If
End If
counter = 2
counter_2 = 0
Next
Console.WriteLine()
Console.WriteLine(number_of_numbers_counter)
Console.ReadLine()
End Sub
Public Function isPrime(ByVal Number As Integer) As Boolean
Dim factors As Integer = 0
For n = 1 To Number
If Number Mod n = 0 Then
factors += 1
End If
Next
If factors > 2 Then
Return False
Else
Return True
End If
End Function
End Module
We can easily generate primes from 1 to 100 by sieve method. Here, I just assign the primes into prime[] array. It's C++ code.
prime[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71, 73,79,83,89,97}
l=25;
// size of prime[]
for(i=0; i<l; i++)
{
for( j=i; j<l; j++ )
{
n = prime[ i ] * prime[ j ];
if( n < 100)
answer.push_back(n);
// value are putting in answer vector.
}
}
printf("The total number is = %d",answer.size());
just list down all the primes upto 50 2,3,5,7,11,13,17,19,23,29,31,37,41,43 and 47 Total = 15
Now 2 can be multiplied by other 14 to give me result<100 Similarly,
3 will give me 8 solutions
5 will give 5 solutions
7 will give me 2 solutions and
11 will give me only 1 solution. Adding all I will get 30 solutions.
In addition to it, I can also have squares of 2,3,5 and 7 as my solution. Therefore, adding all I will get total 34 solutions
3 will give you 9 solutions; 11 will give you 0 solutions (11*13=143).
For an integer to be <100, 1 factor needs to be <10 and other >10. There are 15 prime numbers <50. There are 4 prime no.s <10 (2,3,5,7). The other no. Has to be >10 and - For 2, <50 . So 15-4= 11 no.s..... For 3, <33 . So prime no.include 11,13,17,19,23,29,31. So 7 no.s..... For 5, <20 . So 4 no.s.... For 7, <14 . So 2 no.s.... So total there are -11+7+4+2 numbers = 24 no.s Again 2,3,5,7 can be selected in 4C2 ways = 6. And finally, when digits are repeated , there are 4 no.s (2,3,5,7). Altogether number of ways= 24+6+4=34 ways.
// implementation using c++
using namespace std; int main()
{
int A[16] = {0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47};
int c = 0;
for (int i = 1 ; i <= 100; i++)
{
bool flag = true;
for (int j = 1 ; j <= 15 && flag ; j++)
for (int k = 1 ; k <= 15 && flag ; k++)
if (i == A[j] * A[k]) { c++; flag = false; }
}
cout << c;
}
Problem Loading...
Note Loading...
Set Loading...
Listing the primes from 2 to 47 then you can find:
2 can multiply by 15 numbers
3 can multiply by 10 numbers
5 can multiply by 6 numbers
7 can multiply by 3 numbers
The answer is 3 4